home *** CD-ROM | disk | FTP | other *** search
/ Aminet 8 / Aminet 8 (1995)(GTI - Schatztruhe)[!][Oct 1995].iso / Aminet / dev / gcc / gcc270cp.lha / gnu / lib / g++-include / algo.h < prev    next >
C/C++ Source or Header  |  1995-07-28  |  81KB  |  2,576 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  */
  15.  
  16. #ifndef ALGO_H
  17. #define ALGO_H
  18.  
  19. #include <stdlib.h>
  20. #include <bool.h>
  21. #include <pair.h>
  22. #include <iterator.h>
  23. #include <algobase.h>
  24. #include <heap.h>
  25. #include <tempbuf.h>
  26.  
  27. template <class T>
  28. inline T __median(T a, T b, T c) {
  29.     if (a < b)
  30.     if (b < c)
  31.         return b;
  32.     else if (a < c)
  33.         return c;
  34.     else
  35.         return a;
  36.     else if (a < c)
  37.     return a;
  38.     else if (b < c)
  39.     return c;
  40.     else
  41.     return b;
  42. }
  43.  
  44. template <class T, class Compare>
  45. inline T __median(T a, T b, T c, Compare comp) {
  46.     if (comp(a, b))
  47.     if (comp(b, c))
  48.         return b;
  49.     else if (comp(a, c))
  50.         return c;
  51.     else
  52.         return a;
  53.     else if (comp(a, c))
  54.     return a;
  55.     else if (comp(b, c))
  56.     return c;
  57.     else
  58.     return b;
  59. }
  60.  
  61. template <class InputIterator, class Function>
  62. Function for_each(InputIterator first, InputIterator last, Function f) {
  63.     while (first != last) f(*first++);
  64.     return f;
  65. }
  66.  
  67. template <class InputIterator, class T>
  68. InputIterator find(InputIterator first, InputIterator last, const T& value) {
  69.     while (first != last && *first != value) ++first;
  70.     return first;
  71. }
  72.  
  73. template <class InputIterator, class Predicate>
  74. InputIterator find_if(InputIterator first, InputIterator last,
  75.               Predicate pred) {
  76.     while (first != last && !pred(*first)) ++first;
  77.     return first;
  78. }
  79.  
  80. template <class InputIterator>
  81. InputIterator adjacent_find(InputIterator first, InputIterator last) {
  82.     if (first == last) return last;
  83.     InputIterator next = first;
  84.     while(++next != last) {
  85.     if (*first == *next) return first;
  86.     first = next;
  87.     }
  88.     return last;
  89. }
  90.  
  91. template <class InputIterator, class BinaryPredicate>
  92. InputIterator adjacent_find(InputIterator first, InputIterator last,
  93.                 BinaryPredicate binary_pred) {
  94.     if (first == last) return last;
  95.     InputIterator next = first;
  96.     while(++next != last) {
  97.     if (binary_pred(*first, *next)) return first;
  98.     first = next;
  99.     }
  100.     return last;
  101. }
  102.  
  103. template <class InputIterator, class T, class Size>
  104. void count(InputIterator first, InputIterator last, const T& value,
  105.        Size& n) {
  106.     while (first != last) 
  107.     if (*first++ == value) ++n;
  108. }
  109.  
  110. template <class InputIterator, class Predicate, class Size>
  111. void count_if(InputIterator first, InputIterator last, Predicate pred,
  112.           Size& n) {
  113.     while (first != last)
  114.     if (pred(*first++)) ++n;
  115. }
  116.  
  117. template <class ForwardIterator1, class ForwardIterator2, class Distance>
  118. ForwardIterator1 __search(ForwardIterator1 first1, ForwardIterator1 last1,
  119.               ForwardIterator2 first2, ForwardIterator2 last2,
  120.               Distance*) {
  121.     Distance d1 = 0;
  122.     distance(first1, last1, d1);
  123.     Distance d2 = 0;
  124.     distance(first2, last2, d2);
  125.  
  126.     if (d1 < d2) return last1;
  127.  
  128.     ForwardIterator1 current1 = first1;
  129.     ForwardIterator2 current2 = first2;
  130.  
  131.     while (current2 != last2)
  132.     if (*current1++ != *current2++)
  133.         if (d1-- == d2)
  134.         return last1;
  135.         else {
  136.         current1 = ++first1;
  137.         current2 = first2;
  138.         }
  139.     return (current2 == last2) ? first1 : last1;
  140. }
  141.  
  142. template <class ForwardIterator1, class ForwardIterator2>
  143. inline ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
  144.                    ForwardIterator2 first2, ForwardIterator2 last2)
  145. {
  146.     return __search(first1, last1, first2, last2, distance_type(first1));
  147. }
  148.  
  149. template <class ForwardIterator1, class ForwardIterator2,
  150.       class BinaryPredicate, class Distance>
  151. ForwardIterator1 __search(ForwardIterator1 first1, ForwardIterator1 last1,
  152.               ForwardIterator2 first2, ForwardIterator2 last2,
  153.               BinaryPredicate binary_pred, Distance*) {
  154.     Distance d1 = 0;
  155.     distance(first1, last1, d1);
  156.     Distance d2 = 0;
  157.     distance(first2, last2, d2);
  158.  
  159.     if (d1 < d2) return last1;
  160.  
  161.     ForwardIterator1 current1 = first1;
  162.     ForwardIterator2 current2 = first2;
  163.  
  164.     while (current2 != last2)
  165.     if (!binary_pred(*current1++, *current2++))
  166.         if (d1-- == d2)
  167.         return last1;
  168.         else {
  169.         current1 = ++first1;
  170.         current2 = first2;
  171.         }
  172.     return (current2 == last2) ? first1 : last1;
  173. }
  174.  
  175. template <class ForwardIterator1, class ForwardIterator2,
  176.       class BinaryPredicate>
  177. inline ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
  178.                    ForwardIterator2 first2, ForwardIterator2 last2,
  179.                    BinaryPredicate binary_pred) {
  180.     return __search(first1, last1, first2, last2, binary_pred,
  181.             distance_type(first1));
  182. }
  183.  
  184. template <class ForwardIterator1, class ForwardIterator2>
  185. ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
  186.                  ForwardIterator2 first2) {
  187.     while (first1 != last1) iter_swap(first1++, first2++);
  188.     return first2;
  189. }
  190.  
  191. template <class InputIterator, class OutputIterator, class UnaryOperation>
  192. OutputIterator transform(InputIterator first, InputIterator last,
  193.              OutputIterator result, UnaryOperation op) {
  194.     while (first != last) *result++ = op(*first++);
  195.     return result;
  196. }
  197.  
  198. template <class InputIterator1, class InputIterator2, class OutputIterator,
  199.       class BinaryOperation>
  200. OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
  201.              InputIterator2 first2, OutputIterator result,
  202.              BinaryOperation binary_op) {
  203.     while (first1 != last1) *result++ = binary_op(*first1++, *first2++);
  204.     return result;
  205. }
  206.  
  207. template <class ForwardIterator, class T>
  208. void replace(ForwardIterator first, ForwardIterator last, const T& old_value,
  209.          const T& new_value) {
  210.     while (first != last) {
  211.     if (*first == old_value) *first = new_value;
  212.     ++first;
  213.     }
  214. }
  215.  
  216. template <class ForwardIterator, class Predicate, class T>
  217. void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred,
  218.         const T& new_value) {
  219.     while (first != last) {
  220.     if (pred(*first)) *first = new_value;
  221.     ++first;
  222.     }
  223. }
  224.  
  225. template <class InputIterator, class OutputIterator, class T>
  226. OutputIterator replace_copy(InputIterator first, InputIterator last,
  227.                 OutputIterator result, const T& old_value,
  228.                 const T& new_value) {
  229.     while (first != last) {
  230.     *result++ = *first == old_value ? new_value : *first;
  231.     ++first;
  232.     }
  233.     return result;
  234. }
  235.  
  236. template <class Iterator, class OutputIterator, class Predicate, class T>
  237. OutputIterator replace_copy_if(Iterator first, Iterator last,
  238.                    OutputIterator result, Predicate pred,
  239.                    const T& new_value) {
  240.     while (first != last) {
  241.     *result++ = pred(*first) ? new_value : *first;
  242.     ++first;
  243.     }
  244.     return result;
  245. }
  246.  
  247. template <class ForwardIterator, class Generator>
  248. void generate(ForwardIterator first, ForwardIterator last, Generator gen) {
  249.     while (first != last) *first++ = gen();
  250. }
  251.  
  252. template <class OutputIterator, class Size, class Generator>
  253. void generate_n(OutputIterator first, Size n, Generator gen) {
  254.     while (n-- > 0) *first++ = gen();
  255. }
  256.  
  257. template <class InputIterator, class OutputIterator, class T>
  258. OutputIterator remove_copy(InputIterator first, InputIterator last,
  259.                OutputIterator result, const T& value) {
  260.     while (first != last) {
  261.     if (*first != value) *result++ = *first;
  262.     ++first;
  263.     }
  264.     return result;
  265. }
  266.  
  267. template <class InputIterator, class OutputIterator, class Predicate>
  268. OutputIterator remove_copy_if(InputIterator first, InputIterator last,
  269.                   OutputIterator result, Predicate pred) {
  270.     while (first != last) {
  271.     if (!pred(*first)) *result++ = *first;
  272.     ++first;
  273.     }
  274.     return result;
  275. }
  276.  
  277. template <class ForwardIterator, class T>
  278. ForwardIterator remove(ForwardIterator first, ForwardIterator last,
  279.                const T& value) {
  280.     first = find(first, last, value);
  281.     ForwardIterator next = first;
  282.     return first == last ? first : remove_copy(++next, last, first, value);
  283. }
  284.  
  285. template <class ForwardIterator, class Predicate>
  286. ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
  287.               Predicate pred) {
  288.     first = find_if(first, last, pred);
  289.     ForwardIterator next = first;
  290.     return first == last ? first : remove_copy_if(++next, last, first, pred);
  291. }
  292.  
  293. template <class InputIterator, class ForwardIterator>
  294. ForwardIterator __unique_copy(InputIterator first, InputIterator last,
  295.                   ForwardIterator result, forward_iterator_tag) {
  296.     *result = *first;
  297.     while (++first != last)
  298.         if (*result != *first) *++result = *first;
  299.     return ++result;
  300. }
  301.  
  302. template <class InputIterator, class BidirectionalIterator>
  303. inline BidirectionalIterator __unique_copy(InputIterator first, 
  304.                        InputIterator last,
  305.                                BidirectionalIterator result, 
  306.                            bidirectional_iterator_tag) {
  307.     return __unique_copy(first, last, result, forward_iterator_tag());
  308. }
  309.  
  310. template <class InputIterator, class RandomAccessIterator>
  311. inline RandomAccessIterator __unique_copy(InputIterator first, 
  312.                       InputIterator last,
  313.                              RandomAccessIterator result, 
  314.                          random_access_iterator_tag) {
  315.     return __unique_copy(first, last, result, forward_iterator_tag());
  316. }
  317.  
  318. template <class InputIterator, class OutputIterator, class T>
  319. OutputIterator __unique_copy(InputIterator first, InputIterator last,
  320.                  OutputIterator result, T*) {
  321.     T value = *first;
  322.     *result = value;
  323.     while (++first != last)
  324.     if (value != *first) {
  325.         value = *first;
  326.         *++result = value;
  327.     }
  328.     return ++result;
  329. }
  330.  
  331. template <class InputIterator, class OutputIterator>
  332. inline OutputIterator __unique_copy(InputIterator first, InputIterator last,
  333.                                      OutputIterator result, 
  334.                     output_iterator_tag) {
  335.     return __unique_copy(first, last, result, value_type(first));
  336. }
  337.  
  338. template <class InputIterator, class OutputIterator>
  339. inline OutputIterator unique_copy(InputIterator first, InputIterator last,
  340.                      OutputIterator result) {
  341.     if (first == last) return result;
  342.     return __unique_copy(first, last, result, iterator_category(result));
  343. }
  344. template <class InputIterator, class ForwardIterator, class BinaryPredicate>
  345. ForwardIterator __unique_copy(InputIterator first, InputIterator last,
  346.                   ForwardIterator result, 
  347.                   BinaryPredicate binary_pred,
  348.                   forward_iterator_tag) {
  349.     *result = *first;
  350.     while (++first != last)
  351.         if (!binary_pred(*result, *first)) *++result = *first;
  352.     return ++result;
  353. }
  354.  
  355. template <class InputIterator, class BidirectionalIterator,
  356.           class BinaryPredicate>
  357. inline BidirectionalIterator __unique_copy(InputIterator first, 
  358.                        InputIterator last,
  359.                                BidirectionalIterator result, 
  360.                        BinaryPredicate binary_pred,
  361.                            bidirectional_iterator_tag) {
  362.     return __unique_copy(first, last, result, binary_pred,
  363.              forward_iterator_tag());
  364. }
  365.  
  366. template <class InputIterator, class RandomAccessIterator,
  367.           class BinaryPredicate>
  368. inline RandomAccessIterator __unique_copy(InputIterator first, 
  369.                       InputIterator last,
  370.                              RandomAccessIterator result, 
  371.                       BinaryPredicate binary_pred,
  372.                          random_access_iterator_tag) {
  373.     return __unique_copy(first, last, result, binary_pred, 
  374.              forward_iterator_tag());
  375. }
  376.  
  377. template <class InputIterator, class OutputIterator, class BinaryPredicate,
  378.           class T>
  379. OutputIterator __unique_copy(InputIterator first, InputIterator last,
  380.                  OutputIterator result,
  381.                  BinaryPredicate binary_pred, T*) {
  382.     T value = *first;
  383.     *result = value;
  384.     while (++first != last)
  385.     if (!binary_pred(value, *first)) {
  386.         value = *first;
  387.         *++result = value;
  388.     }
  389.     return ++result;
  390. }
  391.  
  392. template <class InputIterator, class OutputIterator, class BinaryPredicate>
  393. inline OutputIterator __unique_copy(InputIterator first, InputIterator last,
  394.                                      OutputIterator result,
  395.                     BinaryPredicate binary_pred,
  396.                     output_iterator_tag) {
  397.     return __unique_copy(first, last, result, binary_pred, value_type(first));
  398. }
  399.  
  400. template <class InputIterator, class OutputIterator, class BinaryPredicate>
  401. inline OutputIterator unique_copy(InputIterator first, InputIterator last,
  402.                      OutputIterator result,
  403.                   BinaryPredicate binary_pred) {
  404.     if (first == last) return result;
  405.     return __unique_copy(first, last, result, binary_pred,
  406.              iterator_category(result));
  407. }
  408.  
  409. template <class ForwardIterator>
  410. ForwardIterator unique(ForwardIterator first, ForwardIterator last) {
  411.     first = adjacent_find(first, last);
  412.     return unique_copy(first, last, first);
  413. }
  414.  
  415. template <class ForwardIterator, class BinaryPredicate>
  416. ForwardIterator unique(ForwardIterator first, ForwardIterator last,
  417.                BinaryPredicate binary_pred) {
  418.     first = adjacent_find(first, last, binary_pred);
  419.     return unique_copy(first, last, first, binary_pred);
  420. }
  421.  
  422. template <class BidirectionalIterator>
  423. void __reverse(BidirectionalIterator first, BidirectionalIterator last, 
  424.            bidirectional_iterator_tag) {
  425.     while (true)
  426.         if (first == last || first == --last)
  427.         return;
  428.         else
  429.         iter_swap(first++, last);
  430. }
  431.  
  432. template <class RandomAccessIterator>
  433. void __reverse(RandomAccessIterator first, RandomAccessIterator last,
  434.            random_access_iterator_tag) {
  435.     while (first < last) iter_swap(first++, --last);
  436. }
  437.  
  438. template <class BidirectionalIterator>
  439. inline void reverse(BidirectionalIterator first, BidirectionalIterator last) {
  440.     __reverse(first, last, iterator_category(first));
  441. }
  442.  
  443. template <class BidirectionalIterator, class OutputIterator>
  444. OutputIterator reverse_copy(BidirectionalIterator first,
  445.                 BidirectionalIterator last,
  446.                 OutputIterator result) {
  447.     while (first != last) *result++ = *--last;
  448.     return result;
  449. }
  450.  
  451. template <class ForwardIterator, class Distance>
  452. void __rotate(ForwardIterator first, ForwardIterator middle,
  453.           ForwardIterator last, Distance*, forward_iterator_tag) {
  454.     for (ForwardIterator i = middle; ;) {
  455.     iter_swap(first++, i++);
  456.     if (first == middle) {
  457.         if (i == last) return;
  458.         middle = i;
  459.     } else if (i == last)
  460.         i = middle;
  461.     }
  462. }
  463.  
  464. template <class BidirectionalIterator, class Distance>
  465. void __rotate(BidirectionalIterator first, BidirectionalIterator middle,
  466.           BidirectionalIterator last, Distance*,
  467.           bidirectional_iterator_tag) {
  468.     reverse(first, middle);
  469.     reverse(middle, last);
  470.     reverse(first, last);
  471. }
  472.  
  473. template <class EuclideanRingElement>
  474. EuclideanRingElement __gcd(EuclideanRingElement m, EuclideanRingElement n)
  475. {
  476.     while (n != 0) {
  477.     EuclideanRingElement t = m % n;
  478.     m = n;
  479.     n = t;
  480.     }
  481.     return m;
  482. }
  483.  
  484. template <class RandomAccessIterator, class Distance, class T>
  485. void __rotate_cycle(RandomAccessIterator first, RandomAccessIterator last,
  486.             RandomAccessIterator initial, Distance shift, T*) {
  487.     T value = *initial;
  488.     RandomAccessIterator ptr1 = initial;
  489.     RandomAccessIterator ptr2 = ptr1 + shift;
  490.     while (ptr2 != initial) {
  491.     *ptr1 = *ptr2;
  492.     ptr1 = ptr2;
  493.     if (last - ptr2 > shift)
  494.         ptr2 += shift;
  495.     else
  496.         ptr2 = first + (shift - (last - ptr2));
  497.     }
  498.     *ptr1 = value;
  499. }
  500.  
  501. template <class RandomAccessIterator, class Distance>
  502. void __rotate(RandomAccessIterator first, RandomAccessIterator middle,
  503.           RandomAccessIterator last, Distance*,
  504.           random_access_iterator_tag) {
  505.     Distance n = __gcd(last - first, middle - first);
  506.     while (n--)
  507.     __rotate_cycle(first, last, first + n, middle - first,
  508.                value_type(first));
  509. }
  510.  
  511. template <class ForwardIterator>
  512. inline void rotate(ForwardIterator first, ForwardIterator middle,
  513.            ForwardIterator last) {
  514.     if (first == middle || middle == last) return;
  515.     __rotate(first, middle, last, distance_type(first),
  516.          iterator_category(first));
  517. }
  518.  
  519. template <class ForwardIterator, class OutputIterator>
  520. OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle,
  521.                ForwardIterator last, OutputIterator result) {
  522.     return copy(first, middle, copy(middle, last, result));
  523. }
  524.  
  525. unsigned long __long_random(unsigned long);
  526.  
  527. template <class RandomAccessIterator, class Distance>
  528. void __random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
  529.               Distance*) {
  530.     if (first == last) return;
  531.     for (RandomAccessIterator i = first + 1; i != last; ++i)
  532.     iter_swap(i, first + Distance(__long_random((i - first) + 1)));
  533. }
  534.  
  535. template <class RandomAccessIterator>
  536. inline void random_shuffle(RandomAccessIterator first,
  537.                RandomAccessIterator last) {
  538.     __random_shuffle(first, last, distance_type(first));
  539. }
  540.  
  541. template <class RandomAccessIterator, class RandomNumberGenerator>
  542. void random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
  543.             RandomNumberGenerator& __rand) {
  544.     if (first == last) return;
  545.     for (RandomAccessIterator i = first + 1; i != last; ++i)
  546.     iter_swap(i, first + __rand((i - first) + 1));
  547. }
  548.  
  549. template <class BidirectionalIterator, class Predicate>
  550. BidirectionalIterator partition(BidirectionalIterator first,
  551.                 BidirectionalIterator last, Predicate pred) {
  552.     while (true) {
  553.     while (true)
  554.         if (first == last)
  555.         return first;
  556.         else if (pred(*first))
  557.         ++first;
  558.         else
  559.         break;
  560.     --last;
  561.     while (true)
  562.         if (first == last)
  563.         return first;
  564.         else if (!pred(*last))
  565.         --last;
  566.         else
  567.         break;
  568.     iter_swap(first, last);
  569.     ++first;
  570.     }
  571. }
  572.  
  573. template <class ForwardIterator, class Predicate, class Distance>
  574. ForwardIterator __inplace_stable_partition(ForwardIterator first,
  575.                        ForwardIterator last,
  576.                        Predicate pred, Distance len) {
  577.     if (len == 1) return pred(*first) ? last : first;
  578.     ForwardIterator middle = first;
  579.     advance(middle, len / 2);
  580.     ForwardIterator 
  581.     first_cut = __inplace_stable_partition(first, middle, pred, len / 2);
  582.     ForwardIterator 
  583.     second_cut = __inplace_stable_partition(middle, last, pred,
  584.                         len - len / 2);
  585.     rotate(first_cut, middle, second_cut);
  586.     len = 0;
  587.     distance(middle, second_cut, len);
  588.     advance(first_cut, len);
  589.     return first_cut;
  590. }
  591.  
  592. template <class ForwardIterator, class Pointer, class Predicate,
  593.       class Distance, class T>
  594. ForwardIterator __stable_partition_adaptive(ForwardIterator first,
  595.                         ForwardIterator last,
  596.                         Predicate pred, Distance len,
  597.                         Pointer buffer,
  598.                         Distance buffer_size,
  599.                         Distance& fill_pointer, T*) {
  600.     if (len <= buffer_size) {
  601.     len = 0;
  602.     ForwardIterator result1 = first;
  603.     Pointer result2 = buffer;
  604.     while (first != last && len < fill_pointer)
  605.         if (pred(*first))
  606.         *result1++ = *first++;
  607.         else {
  608.         *result2++ = *first++;
  609.         ++len;
  610.         }
  611.     if (first != last) {
  612.         raw_storage_iterator<Pointer, T> result3 = result2;
  613.         while (first != last)           
  614.         if (pred(*first))
  615.             *result1++ = *first++;
  616.         else {
  617.             *result3++ = *first++;
  618.             ++len;
  619.         }
  620.         fill_pointer = len;
  621.     }
  622.     copy(buffer, buffer + len, result1);
  623.     return result1;
  624.     }
  625.     ForwardIterator middle = first;
  626.     advance(middle, len / 2);
  627.     ForwardIterator first_cut = __stable_partition_adaptive
  628.     (first, middle, pred, len / 2, buffer, buffer_size, fill_pointer, 
  629.      (T*)0);
  630.     ForwardIterator second_cut = __stable_partition_adaptive
  631.     (middle, last, pred, len - len / 2, buffer, buffer_size, 
  632.      fill_pointer, (T*)0);
  633.     rotate(first_cut, middle, second_cut);
  634.     len = 0;
  635.     distance(middle, second_cut, len);
  636.     advance(first_cut, len);
  637.     return first_cut;
  638. }
  639.  
  640. template <class ForwardIterator, class Predicate, class Pointer,
  641.       class Distance>
  642. ForwardIterator __stable_partition(ForwardIterator first, ForwardIterator last,
  643.                    Predicate pred, Distance len,
  644.                    pair<Pointer, Distance> p) {
  645.     if (p.first == 0)
  646.     return __inplace_stable_partition(first, last, pred, len);
  647.     Distance fill_pointer = 0;
  648.     ForwardIterator result = 
  649.     __stable_partition_adaptive(first, last, pred, len, p.first, p.second,
  650.                     fill_pointer, value_type(first)); 
  651.     destroy(p.first, p.first + fill_pointer);
  652.     return_temporary_buffer(p.first);
  653.     return result;
  654. }
  655.  
  656. template <class ForwardIterator, class Predicate, class Distance>
  657. inline ForwardIterator __stable_partition_aux(ForwardIterator first,
  658.                           ForwardIterator last, 
  659.                           Predicate pred, Distance*) {
  660.     Distance len = 0;
  661.     distance(first, last, len);
  662.     return __stable_partition(first, last, pred, len,
  663.                   get_temporary_buffer(len, value_type(first)));
  664. }
  665.  
  666. template <class ForwardIterator, class Predicate>
  667. inline ForwardIterator stable_partition(ForwardIterator first,
  668.                     ForwardIterator last, 
  669.                     Predicate pred) {
  670.     return __stable_partition_aux(first, last, pred, distance_type(first));
  671. }
  672.  
  673. template <class RandomAccessIterator, class T>
  674. RandomAccessIterator __unguarded_partition(RandomAccessIterator first, 
  675.                        RandomAccessIterator last, 
  676.                        T pivot) {
  677.     while (1) {
  678.     while (*first < pivot) ++first;
  679.     --last;
  680.     while (pivot < *last) --last;
  681.     if (!(first < last)) return first;
  682.     iter_swap(first, last);
  683.     ++first;
  684.     }
  685. }    
  686.  
  687. template <class RandomAccessIterator, class T, class Compare>
  688. RandomAccessIterator __unguarded_partition(RandomAccessIterator first, 
  689.                        RandomAccessIterator last, 
  690.                        T pivot, Compare comp) {
  691.     while (1) {
  692.     while (comp(*first, pivot)) ++first;
  693.     --last;
  694.     while (comp(pivot, *last)) --last;
  695.     if (!(first < last)) return first;
  696.     iter_swap(first, last);
  697.     ++first;
  698.     }
  699. }
  700.  
  701. const int __stl_threshold = 16;
  702.  
  703. template <class RandomAccessIterator, class T>
  704. void __quick_sort_loop_aux(RandomAccessIterator first,
  705.                RandomAccessIterator last, T*) {
  706.     while (last - first > __stl_threshold) {
  707.     RandomAccessIterator cut = __unguarded_partition
  708.         (first, last, T(__median(*first, *(first + (last - first)/2),
  709.                      *(last - 1))));
  710.     if (cut - first >= last - cut) {
  711.         __quick_sort_loop(cut, last);
  712.         last = cut;
  713.     } else {
  714.         __quick_sort_loop(first, cut);
  715.         first = cut;
  716.     }
  717.     }
  718. }
  719.  
  720. template <class RandomAccessIterator>
  721. inline void __quick_sort_loop(RandomAccessIterator first,
  722.                   RandomAccessIterator last) {
  723.     __quick_sort_loop_aux(first, last, value_type(first));
  724. }
  725.  
  726. template <class RandomAccessIterator, class T, class Compare>
  727. void __quick_sort_loop_aux(RandomAccessIterator first, 
  728.                RandomAccessIterator last, T*, Compare comp) {
  729.     while (last - first > __stl_threshold) {
  730.     RandomAccessIterator cut = __unguarded_partition
  731.         (first, last, T(__median(*first, *(first + (last - first)/2), 
  732.                    *(last - 1), comp)), comp);
  733.     if (cut - first >= last - cut) {
  734.         __quick_sort_loop(cut, last, comp);
  735.         last = cut;
  736.     } else {
  737.         __quick_sort_loop(first, cut, comp);
  738.         first = cut;
  739.     }
  740.     }
  741. }
  742.  
  743. template <class RandomAccessIterator, class Compare>
  744. inline void __quick_sort_loop(RandomAccessIterator first, 
  745.                   RandomAccessIterator last, Compare comp) {
  746.     __quick_sort_loop_aux(first, last, value_type(first), comp);
  747. }
  748.  
  749. template <class RandomAccessIterator, class T>
  750. void __unguarded_linear_insert(RandomAccessIterator last, T value) {
  751.     RandomAccessIterator next = last;
  752.     --next;
  753.     while (value < *next) {
  754.     *last = *next;
  755.     last = next--;
  756.     }
  757.     *last = value;
  758. }
  759.  
  760. template <class RandomAccessIterator, class T, class Compare>
  761. void __unguarded_linear_insert(RandomAccessIterator last, T value, 
  762.                    Compare comp) {
  763.     RandomAccessIterator next = last;
  764.     --next;  
  765.     while (comp(value , *next)) {
  766.     *last = *next;
  767.     last = next--;
  768.     }
  769.     *last = value;
  770. }
  771.  
  772. template <class RandomAccessIterator, class T>
  773. inline void __linear_insert(RandomAccessIterator first, 
  774.                 RandomAccessIterator last, T*) {
  775.     T value = *last;
  776.     if (value < *first) {
  777.     copy_backward(first, last, last + 1);
  778.     *first = value;
  779.     } else
  780.     __unguarded_linear_insert(last, value);
  781. }
  782.  
  783. template <class RandomAccessIterator, class T, class Compare>
  784. inline void __linear_insert(RandomAccessIterator first, 
  785.                 RandomAccessIterator last, T*, Compare comp) {
  786.     T value = *last;
  787.     if (comp(value, *first)) {
  788.     copy_backward(first, last, last + 1);
  789.     *first = value;
  790.     } else
  791.     __unguarded_linear_insert(last, value, comp);
  792. }
  793.  
  794. template <class RandomAccessIterator>
  795. void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
  796.     if (first == last) return; 
  797.     for (RandomAccessIterator i = first + 1; i != last; ++i)
  798.     __linear_insert(first, i, value_type(first));
  799. }
  800.  
  801. template <class RandomAccessIterator, class Compare>
  802. void __insertion_sort(RandomAccessIterator first,
  803.               RandomAccessIterator last, Compare comp) {
  804.     if (first == last) return;
  805.     for (RandomAccessIterator i = first + 1; i != last; ++i)
  806.     __linear_insert(first, i, value_type(first), comp);
  807. }
  808.  
  809. template <class RandomAccessIterator, class T>
  810. void __unguarded_insertion_sort_aux(RandomAccessIterator first, 
  811.                     RandomAccessIterator last, T*) {
  812.     for (RandomAccessIterator i = first; i != last; ++i)
  813.     __unguarded_linear_insert(i, T(*i));
  814. }
  815.  
  816. template <class RandomAccessIterator>
  817. inline void __unguarded_insertion_sort(RandomAccessIterator first, 
  818.                 RandomAccessIterator last) {
  819.     __unguarded_insertion_sort_aux(first, last, value_type(first));
  820. }
  821.  
  822. template <class RandomAccessIterator, class T, class Compare>
  823. void __unguarded_insertion_sort_aux(RandomAccessIterator first, 
  824.                     RandomAccessIterator last,
  825.                     T*, Compare comp) {
  826.     for (RandomAccessIterator i = first; i != last; ++i)
  827.     __unguarded_linear_insert(i, T(*i), comp);
  828. }
  829.  
  830. template <class RandomAccessIterator, class Compare>
  831. inline void __unguarded_insertion_sort(RandomAccessIterator first, 
  832.                        RandomAccessIterator last,
  833.                        Compare comp) {
  834.     __unguarded_insertion_sort_aux(first, last, value_type(first), comp);
  835. }
  836.  
  837. template <class RandomAccessIterator>
  838. void __final_insertion_sort(RandomAccessIterator first, 
  839.                 RandomAccessIterator last) {
  840.     if (last - first > __stl_threshold) {
  841.     __insertion_sort(first, first + __stl_threshold);
  842.     __unguarded_insertion_sort(first + __stl_threshold, last);
  843.     } else
  844.     __insertion_sort(first, last);
  845. }
  846.  
  847. template <class RandomAccessIterator, class Compare>
  848. void __final_insertion_sort(RandomAccessIterator first, 
  849.                 RandomAccessIterator last, Compare comp) {
  850.     if (last - first > __stl_threshold) {
  851.     __insertion_sort(first, first + __stl_threshold, comp);
  852.     __unguarded_insertion_sort(first + __stl_threshold, last, comp);
  853.     } else
  854.     __insertion_sort(first, last, comp);
  855. }
  856.  
  857. template <class RandomAccessIterator>
  858. void sort(RandomAccessIterator first, RandomAccessIterator last) {
  859.     __quick_sort_loop(first, last);
  860.     __final_insertion_sort(first, last);
  861. }
  862.  
  863. template <class RandomAccessIterator, class Compare>
  864. void sort(RandomAccessIterator first, RandomAccessIterator last,
  865.       Compare comp) {
  866.    __quick_sort_loop(first, last, comp);
  867.    __final_insertion_sort(first, last, comp);
  868. }
  869.  
  870. template <class RandomAccessIterator>
  871. void __inplace_stable_sort(RandomAccessIterator first,
  872.                RandomAccessIterator last) {
  873.     if (last - first < 15) {
  874.     __insertion_sort(first, last);
  875.     return;
  876.     }
  877.     RandomAccessIterator middle = first + (last - first) / 2;
  878.     __inplace_stable_sort(first, middle);
  879.     __inplace_stable_sort(middle, last);
  880.     __merge_without_buffer(first, middle, last, middle - first, last - middle);
  881. }
  882.  
  883. template <class RandomAccessIterator, class Compare>
  884. void __inplace_stable_sort(RandomAccessIterator first,
  885.                RandomAccessIterator last, Compare comp) {
  886.     if (last - first < 15) {
  887.     __insertion_sort(first, last, comp);
  888.     return;
  889.     }
  890.     RandomAccessIterator middle = first + (last - first) / 2;
  891.     __inplace_stable_sort(first, middle, comp);
  892.     __inplace_stable_sort(middle, last, comp);
  893.     __merge_without_buffer(first, middle, last, middle - first,
  894.                last - middle, comp);
  895. }
  896.  
  897. template <class RandomAccessIterator1, class RandomAccessIterator2,
  898.       class RandomAccessIterator3, class Distance, class T>
  899. RandomAccessIterator3 __merge_aux(RandomAccessIterator1 first1,
  900.                   RandomAccessIterator1 last1,
  901.                   RandomAccessIterator2 first2,
  902.                   RandomAccessIterator2 last2,
  903.                   RandomAccessIterator3 result,
  904.                   Distance& fill_pointer, T*){
  905.     Distance len = 0;
  906.     while (first1 != last1 && first2 != last2 && len < fill_pointer) {
  907.     ++len;
  908.     if (*first2 < *first1)
  909.         *result++ = *first2++;
  910.     else
  911.         *result++ = *first1++;
  912.     }
  913.     if (fill_pointer == len) {
  914.     raw_storage_iterator<RandomAccessIterator3, T> p = result;
  915.     result += (last1 - first1) + (last2 - first2);
  916.     fill_pointer += (last1 - first1) + (last2 - first2);
  917.     while (first1 != last1 && first2 != last2)
  918.         if (*first2 < *first1)
  919.         *p++ = *first2++;
  920.         else
  921.         *p++ = *first1++;
  922.     copy(first2, last2, copy(first1, last1, p));
  923.     } else if (first2 == last2) {
  924.     while (first1 != last1 && len < fill_pointer) { 
  925.         ++len;
  926.         *result++ = *first1++;
  927.     }
  928.     if (fill_pointer == len) {
  929.         raw_storage_iterator<RandomAccessIterator3, T> p = result;  
  930.         result += last1 - first1;
  931.         fill_pointer += last1 - first1;
  932.         while (first1 != last1) *p++ = *first1++;
  933.     }
  934.     } else {
  935.     while (first2 != last2 && len < fill_pointer) { 
  936.         ++len;
  937.         *result++ = *first2++;
  938.     }
  939.     if (fill_pointer == len) {
  940.         raw_storage_iterator<RandomAccessIterator3, T> p = result;  
  941.         result += last2 - first2;
  942.         fill_pointer += last2 - first2;
  943.         while (first2 != last2) *p++ = *first2++;
  944.     }
  945.     }
  946.     return result;
  947. }       
  948.  
  949. template <class RandomAccessIterator1, class RandomAccessIterator2,
  950.       class RandomAccessIterator3, class Distance, class T, class Compare>
  951. RandomAccessIterator3 __merge_aux(RandomAccessIterator1 first1,
  952.                   RandomAccessIterator1 last1,
  953.                   RandomAccessIterator2 first2,
  954.                   RandomAccessIterator2 last2,
  955.                   RandomAccessIterator3 result,
  956.                   Distance& fill_pointer, T*, Compare comp){
  957.     Distance len = 0;
  958.     while (first1 != last1 && first2 != last2 && len < fill_pointer) {
  959.     ++len;
  960.     if (comp(*first2, *first1))
  961.         *result++ = *first2++;
  962.     else
  963.         *result++ = *first1++;
  964.     }
  965.     if (fill_pointer <= len) {
  966.     raw_storage_iterator<RandomAccessIterator3, T> p = result;
  967.     result += (last1 - first1) + (last2 - first2);
  968.     fill_pointer += (last1 - first1) + (last2 - first2);
  969.     while (first1 != last1 && first2 != last2)
  970.         if (comp(*first2, *first1))
  971.         *p++ = *first2++;
  972.         else
  973.         *p++ = *first1++;
  974.     copy(first2, last2, copy(first1, last1, p));
  975.     } else if (first2 == last2) {
  976.     while (first1 != last1 && len < fill_pointer) { 
  977.         ++len;
  978.         *result++ = *first1++;
  979.     }
  980.     if (fill_pointer == len) {
  981.         raw_storage_iterator<RandomAccessIterator3, T> p = result;  
  982.         result += last1 - first1;
  983.         fill_pointer += last1 - first1;
  984.         while (first1 != last1) *p++ = *first1++;
  985.     }
  986.     } else {
  987.     while (first2 != last2 && len < fill_pointer) { 
  988.         ++len;
  989.         *result++ = *first2++;
  990.     }
  991.     if (fill_pointer == len) {
  992.         raw_storage_iterator<RandomAccessIterator3, T> p = result;  
  993.         result += last2 - first2;
  994.         fill_pointer += last2 - first2;
  995.         while (first2 != last2) *p++ = *first2++;
  996.     }
  997.     }
  998.     return result;
  999. }       
  1000.  
  1001. template <class RandomAccessIterator1, class RandomAccessIterator2,
  1002.       class Distance, class T>
  1003. void __merge_sort_loop_aux(RandomAccessIterator1 first,
  1004.                RandomAccessIterator1 last, 
  1005.                RandomAccessIterator2 result, Distance step_size,
  1006.                Distance& fill_pointer, T*) {
  1007.     Distance two_step = 2 * step_size;
  1008.  
  1009.     while (last - first >= two_step) {
  1010.     result = __merge_aux(first, first + step_size, first + step_size,
  1011.                  first + two_step, result, fill_pointer, (T*)0);
  1012.     first += two_step;
  1013.     }
  1014.     step_size = min(Distance(last - first), step_size);
  1015.  
  1016.     __merge_aux(first, first + step_size, first + step_size, last, result,
  1017.         fill_pointer, (T*)0);
  1018. }
  1019.  
  1020. template <class RandomAccessIterator1, class RandomAccessIterator2,
  1021.       class Distance, class T, class Compare>
  1022. void __merge_sort_loop_aux(RandomAccessIterator1 first,
  1023.                RandomAccessIterator1 last, 
  1024.                RandomAccessIterator2 result, Distance step_size,
  1025.                Distance& fill_pointer, T*, Compare comp) {
  1026.     Distance two_step = 2 * step_size;
  1027.  
  1028.     while (last - first >= two_step) {
  1029.     result = __merge_aux(first, first + step_size, first + step_size, 
  1030.                  first + two_step, result, fill_pointer, (T*)0,
  1031.                  comp);
  1032.     first += two_step;
  1033.     }
  1034.     step_size = min(Distance(last - first), step_size);
  1035.  
  1036.     __merge_aux(first, first + step_size, first + step_size, last, result, 
  1037.         fill_pointer, (T*)0, comp);
  1038. }
  1039.  
  1040. template <class RandomAccessIterator1, class RandomAccessIterator2,
  1041.       class Distance>
  1042. void __merge_sort_loop(RandomAccessIterator1 first,
  1043.                RandomAccessIterator1 last, 
  1044.                RandomAccessIterator2 result, Distance step_size) {
  1045.     Distance two_step = 2 * step_size;
  1046.  
  1047.     while (last - first >= two_step) {
  1048.     result = merge(first, first + step_size,
  1049.                first + step_size, first + two_step, result);
  1050.     first += two_step;
  1051.     }
  1052.     step_size = min(Distance(last - first), step_size);
  1053.  
  1054.     merge(first, first + step_size, first + step_size, last, result);
  1055. }
  1056.  
  1057. template <class RandomAccessIterator1, class RandomAccessIterator2,
  1058.       class Distance, class Compare>
  1059. void __merge_sort_loop(RandomAccessIterator1 first,
  1060.                RandomAccessIterator1 last, 
  1061.                RandomAccessIterator2 result, Distance step_size,
  1062.                Compare comp) {
  1063.     Distance two_step = 2 * step_size;
  1064.  
  1065.     while (last - first >= two_step) {
  1066.     result = merge(first, first + step_size,
  1067.                first + step_size, first + two_step, result, comp);
  1068.     first += two_step;
  1069.     }
  1070.     step_size = min(Distance(last - first), step_size);
  1071.  
  1072.     merge(first, first + step_size, first + step_size, last, result, comp);
  1073. }
  1074.  
  1075. const int __stl_chunk_size = 7;
  1076.     
  1077. template <class RandomAccessIterator, class Distance>
  1078. void __chunk_insertion_sort(RandomAccessIterator first, 
  1079.                   RandomAccessIterator last, Distance chunk_size) {
  1080.     while (last - first >= chunk_size) {
  1081.     __insertion_sort(first, first + chunk_size);
  1082.     first += chunk_size;
  1083.     }
  1084.     __insertion_sort(first, last);
  1085. }
  1086.  
  1087. template <class RandomAccessIterator, class Distance, class Compare>
  1088. void __chunk_insertion_sort(RandomAccessIterator first, 
  1089.                 RandomAccessIterator last,
  1090.                 Distance chunk_size, Compare comp) {
  1091.     while (last - first >= chunk_size) {
  1092.     __insertion_sort(first, first + chunk_size, comp);
  1093.     first += chunk_size;
  1094.     }
  1095.     __insertion_sort(first, last, comp);
  1096. }
  1097.  
  1098. template <class RandomAccessIterator, class Pointer, class Distance, class T>
  1099. void __merge_sort_with_buffer(RandomAccessIterator first, 
  1100.                    RandomAccessIterator last,
  1101.                    Pointer buffer, Distance& fill_pointer, T*) {
  1102.     Distance len = last - first;
  1103.     Pointer buffer_last = buffer + len;
  1104.  
  1105.     Distance step_size = __stl_chunk_size;
  1106.     __chunk_insertion_sort(first, last, step_size);
  1107.     while (step_size < len) {
  1108.     __merge_sort_loop_aux(first, last, buffer, step_size, fill_pointer,
  1109.                   (T*)0);
  1110.     step_size *= 2;
  1111.     __merge_sort_loop(buffer, buffer_last, first, step_size);
  1112.     step_size *= 2;
  1113.     }
  1114. }
  1115.  
  1116. template <class RandomAccessIterator, class Pointer, class Distance, class T,
  1117.       class Compare>
  1118. void __merge_sort_with_buffer(RandomAccessIterator first, 
  1119.                   RandomAccessIterator last,
  1120.                   Pointer buffer, Distance& fill_pointer,
  1121.                   T*, Compare comp) {
  1122.     Distance len = last - first;
  1123.     Pointer buffer_last = buffer + len;
  1124.  
  1125.     Distance step_size = __stl_chunk_size;
  1126.     __chunk_insertion_sort(first, last, step_size, comp);
  1127.  
  1128.     while (step_size < len) {
  1129.     __merge_sort_loop_aux(first, last, buffer, step_size, fill_pointer,
  1130.                   (T*)0, comp);
  1131.     step_size *= 2;
  1132.     __merge_sort_loop(buffer, buffer_last, first, step_size, comp);
  1133.     step_size *= 2;
  1134.     }
  1135. }
  1136.  
  1137. template <class RandomAccessIterator, class Pointer, class Distance, class T>
  1138. void __stable_sort_adaptive(RandomAccessIterator first, 
  1139.                 RandomAccessIterator last, Pointer buffer,
  1140.                 Distance buffer_size, Distance& fill_pointer, T*) {
  1141.     Distance len = (last - first + 1) / 2;
  1142.     RandomAccessIterator middle = first + len;
  1143.     if (len > buffer_size) {
  1144.     __stable_sort_adaptive(first, middle, buffer, buffer_size,
  1145.                    fill_pointer, (T*)0);
  1146.     __stable_sort_adaptive(middle, last, buffer, buffer_size,
  1147.                    fill_pointer, (T*)0);
  1148.     } else {
  1149.     __merge_sort_with_buffer(first, middle, buffer, fill_pointer, (T*)0);
  1150.     __merge_sort_with_buffer(middle, last, buffer, fill_pointer, (T*)0);
  1151.     }
  1152.     __merge_adaptive(first, middle, last, Distance(middle - first), 
  1153.              Distance(last - middle), buffer, buffer_size,
  1154.              fill_pointer, (T*)0);
  1155. }
  1156.  
  1157. template <class RandomAccessIterator, class Pointer, class Distance, class T,
  1158.       class Compare>
  1159. void __stable_sort_adaptive(RandomAccessIterator first, 
  1160.                 RandomAccessIterator last, Pointer buffer,
  1161.                 Distance buffer_size, Distance& fill_pointer, 
  1162.                 T*, Compare comp) {
  1163.     Distance len = (last - first + 1) / 2;
  1164.     RandomAccessIterator middle = first + len;
  1165.     if (len > buffer_size) {
  1166.     __stable_sort_adaptive(first, middle, buffer, buffer_size,
  1167.                    fill_pointer, (T*)0, comp);
  1168.     __stable_sort_adaptive(middle, last, buffer, buffer_size,
  1169.                    fill_pointer, (T*)0, comp);
  1170.     } else {
  1171.     __merge_sort_with_buffer(first, middle, buffer, fill_pointer,
  1172.                  (T*)0, comp);
  1173.     __merge_sort_with_buffer(middle, last, buffer, fill_pointer,
  1174.                  (T*)0, comp);
  1175.     }
  1176.     __merge_adaptive(first, middle, last, Distance(middle - first), 
  1177.              Distance(last - middle), buffer, buffer_size,
  1178.              fill_pointer, (T*)0, comp);
  1179. }
  1180.  
  1181. template <class RandomAccessIterator, class Pointer, class Distance>
  1182. inline void __stable_sort(RandomAccessIterator first,
  1183.               RandomAccessIterator last,
  1184.               pair<Pointer, Distance> p) {
  1185.     if (p.first == 0) {
  1186.     __inplace_stable_sort(first, last);
  1187.     return;
  1188.     }
  1189.     Distance fill_pointer = 0;
  1190.     __stable_sort_adaptive(first, last, p.first, p.second, fill_pointer,
  1191.                value_type(first));
  1192.     destroy(p.first, p.first + fill_pointer);
  1193.     return_temporary_buffer(p.first);
  1194. }
  1195.  
  1196. template <class RandomAccessIterator, class Pointer, class Distance,
  1197.       class Compare>
  1198. inline void __stable_sort(RandomAccessIterator first,
  1199.               RandomAccessIterator last,
  1200.               pair<Pointer, Distance> p, Compare comp) {
  1201.     if (p.first == 0) {
  1202.     __inplace_stable_sort(first, last, comp);
  1203.     return;
  1204.     }
  1205.     Distance fill_pointer = 0;
  1206.     __stable_sort_adaptive(first, last, p.first, p.second, fill_pointer,
  1207.                value_type(first), comp);
  1208.     destroy(p.first, p.first + fill_pointer);
  1209.     return_temporary_buffer(p.first);
  1210. }
  1211.  
  1212. template <class RandomAccessIterator, class Distance>
  1213. inline void __stable_sort_aux(RandomAccessIterator first,
  1214.                   RandomAccessIterator last, Distance*) {
  1215.     __stable_sort(first, last, get_temporary_buffer(Distance(last - first),
  1216.                             value_type(first)));
  1217. }
  1218.  
  1219. template <class RandomAccessIterator, class Distance, class Compare>
  1220. inline void __stable_sort_aux(RandomAccessIterator first,
  1221.                   RandomAccessIterator last, Distance*,
  1222.                   Compare comp) {
  1223.     __stable_sort(first, last, get_temporary_buffer(Distance(last - first),
  1224.                             value_type(first)), comp);
  1225. }
  1226.  
  1227. template <class RandomAccessIterator>
  1228. inline void stable_sort(RandomAccessIterator first,
  1229.             RandomAccessIterator last) {
  1230.     __stable_sort_aux(first, last, distance_type(first));
  1231. }
  1232.  
  1233. template <class RandomAccessIterator, class Compare>
  1234. inline void stable_sort(RandomAccessIterator first,
  1235.             RandomAccessIterator last, Compare comp) {
  1236.     __stable_sort_aux(first, last, distance_type(first), comp);
  1237. }
  1238.  
  1239. template <class RandomAccessIterator, class T>
  1240. void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
  1241.             RandomAccessIterator last, T*) {
  1242.     make_heap(first, middle);
  1243.     for (RandomAccessIterator i = middle; i < last; ++i)
  1244.     if (*i < *first) 
  1245.       __pop_heap(first, middle, i, T(*i), distance_type(first));
  1246.     sort_heap(first, middle);
  1247. }
  1248.  
  1249. template <class RandomAccessIterator>
  1250. inline void partial_sort(RandomAccessIterator first,
  1251.              RandomAccessIterator middle,
  1252.              RandomAccessIterator last) {
  1253.     __partial_sort(first, middle, last, value_type(first));
  1254. }
  1255.  
  1256. template <class RandomAccessIterator, class T, class Compare>
  1257. void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
  1258.             RandomAccessIterator last, T*, Compare comp) {
  1259.     make_heap(first, middle, comp);
  1260.     for (RandomAccessIterator i = middle; i < last; ++i)
  1261.     if (*i < *first) 
  1262.       __pop_heap(first, middle, i, T(*i), comp, distance_type(first));
  1263.     sort_heap(first, middle, comp);
  1264. }
  1265.  
  1266. template <class RandomAccessIterator, class Compare>
  1267. inline void partial_sort(RandomAccessIterator first,
  1268.              RandomAccessIterator middle,
  1269.              RandomAccessIterator last, Compare comp) {
  1270.     __partial_sort(first, middle, last, value_type(first), comp);
  1271. }
  1272.  
  1273. template <class InputIterator, class RandomAccessIterator, class Distance,
  1274.           class T>
  1275. RandomAccessIterator __partial_sort_copy(InputIterator first,
  1276.                      InputIterator last,
  1277.                      RandomAccessIterator result_first,
  1278.                      RandomAccessIterator result_last, 
  1279.                      Distance*, T*) {
  1280.     if (result_first == result_last) return result_last;
  1281.     RandomAccessIterator result_real_last = result_first;
  1282.     while(first != last && result_real_last != result_last)
  1283.     *result_real_last++ = *first++;
  1284.     make_heap(result_first, result_real_last);
  1285.     while (first != last) {
  1286.     if (*first < *result_first) 
  1287.         __adjust_heap(result_first, Distance(0),
  1288.               Distance(result_real_last - result_first), T(*first));
  1289.     ++first;
  1290.     }
  1291.     sort_heap(result_first, result_real_last);
  1292.     return result_real_last;
  1293. }
  1294.  
  1295. template <class InputIterator, class RandomAccessIterator>
  1296. inline RandomAccessIterator
  1297. partial_sort_copy(InputIterator first, InputIterator last,
  1298.           RandomAccessIterator result_first,
  1299.           RandomAccessIterator result_last) {
  1300.     return __partial_sort_copy(first, last, result_first, result_last, 
  1301.                    distance_type(result_first), value_type(first));
  1302. }
  1303.  
  1304. template <class InputIterator, class RandomAccessIterator, class Compare,
  1305.           class Distance, class T>
  1306. RandomAccessIterator __partial_sort_copy(InputIterator first,
  1307.                      InputIterator last,
  1308.                      RandomAccessIterator result_first,
  1309.                      RandomAccessIterator result_last,
  1310.                      Compare comp, Distance*, T*) {
  1311.     if (result_first == result_last) return result_last;
  1312.     RandomAccessIterator result_real_last = result_first;
  1313.     while(first != last && result_real_last != result_last)
  1314.     *result_real_last++ = *first++;
  1315.     make_heap(result_first, result_real_last, comp);
  1316.     while (first != last) {
  1317.     if (*first < *result_first) 
  1318.         __adjust_heap(result_first, Distance(0),
  1319.               Distance(result_real_last - result_first), T(*first),
  1320.               comp);
  1321.     ++first;
  1322.     }
  1323.     sort_heap(result_first, result_real_last, comp);
  1324.     return result_real_last;
  1325. }
  1326.  
  1327. template <class InputIterator, class RandomAccessIterator, class Compare>
  1328. inline RandomAccessIterator
  1329. partial_sort_copy(InputIterator first, InputIterator last,
  1330.           RandomAccessIterator result_first,
  1331.           RandomAccessIterator result_last, Compare comp) {
  1332.     return __partial_sort_copy(first, last, result_first, result_last, comp,
  1333.                    distance_type(result_first), value_type(first));
  1334. }
  1335.  
  1336. template <class RandomAccessIterator, class T>
  1337. void __nth_element(RandomAccessIterator first, RandomAccessIterator nth,
  1338.            RandomAccessIterator last, T*) {
  1339.     while (last - first > 3) {
  1340.     RandomAccessIterator cut = __unguarded_partition
  1341.         (first, last, T(__median(*first, *(first + (last - first)/2),
  1342.                      *(last - 1))));
  1343.     if (cut <= nth)
  1344.         first = cut;
  1345.     else 
  1346.         last = cut;
  1347.     }
  1348.     __insertion_sort(first, last);
  1349. }
  1350.  
  1351. template <class RandomAccessIterator>
  1352. inline void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
  1353.             RandomAccessIterator last) {
  1354.     __nth_element(first, nth, last, value_type(first));
  1355. }
  1356.  
  1357. template <class RandomAccessIterator, class T, class Compare>
  1358. void __nth_element(RandomAccessIterator first, RandomAccessIterator nth,
  1359.            RandomAccessIterator last, T*, Compare comp) {
  1360.     while (last - first > 3) {
  1361.     RandomAccessIterator cut = __unguarded_partition
  1362.         (first, last, T(__median(*first, *(first + (last - first)/2), 
  1363.                      *(last - 1), comp)), comp);
  1364.     if (cut <= nth)
  1365.         first = cut;
  1366.     else 
  1367.         last = cut;
  1368.     }
  1369.     __insertion_sort(first, last, comp);
  1370. }
  1371.  
  1372. template <class RandomAccessIterator, class Compare>
  1373. inline void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
  1374.          RandomAccessIterator last, Compare comp) {
  1375.     __nth_element(first, nth, last, value_type(first), comp);
  1376. }
  1377.  
  1378. template <class ForwardIterator, class T, class Distance>
  1379. ForwardIterator __lower_bound(ForwardIterator first, ForwardIterator last,
  1380.                   const T& value, Distance*,
  1381.                   forward_iterator_tag) {
  1382.     Distance len = 0;
  1383.     distance(first, last, len);
  1384.     Distance half;
  1385.     ForwardIterator middle;
  1386.  
  1387.     while (len > 0) {
  1388.     half = len / 2;
  1389.     middle = first;
  1390.     advance(middle, half);
  1391.     if (*middle < value) {
  1392.         first = middle;
  1393.         ++first;
  1394.         len = len - half - 1;
  1395.     } else
  1396.         len = half;
  1397.     }
  1398.     return first;
  1399. }
  1400.  
  1401. template <class ForwardIterator, class T, class Distance>
  1402. inline ForwardIterator __lower_bound(ForwardIterator first,
  1403.                      ForwardIterator last,
  1404.                      const T& value, Distance*,
  1405.                      bidirectional_iterator_tag) {
  1406.     return __lower_bound(first, last, value, (Distance*)0,
  1407.              forward_iterator_tag());
  1408. }
  1409.  
  1410. template <class RandomAccessIterator, class T, class Distance>
  1411. RandomAccessIterator __lower_bound(RandomAccessIterator first,
  1412.                    RandomAccessIterator last, const T& value,
  1413.                    Distance*, random_access_iterator_tag) {
  1414.     Distance len = last - first;
  1415.     Distance half;
  1416.     RandomAccessIterator middle;
  1417.  
  1418.     while (len > 0) {
  1419.     half = len / 2;
  1420.     middle = first + half;
  1421.     if (*middle < value) {
  1422.         first = middle + 1;
  1423.         len = len - half - 1;
  1424.     } else
  1425.         len = half;
  1426.     }
  1427.     return first;
  1428. }
  1429.  
  1430. template <class ForwardIterator, class T>
  1431. inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
  1432.                    const T& value) {
  1433.     return __lower_bound(first, last, value, distance_type(first),
  1434.              iterator_category(first));
  1435. }
  1436.  
  1437. template <class ForwardIterator, class T, class Compare, class Distance>
  1438. ForwardIterator __lower_bound(ForwardIterator first, ForwardIterator last,
  1439.                   const T& value, Compare comp, Distance*,
  1440.                   forward_iterator_tag) {
  1441.     Distance len = 0;
  1442.     distance(first, last, len);
  1443.     Distance half;
  1444.     ForwardIterator middle;
  1445.  
  1446.     while (len > 0) {
  1447.     half = len / 2;
  1448.     middle = first;
  1449.     advance(middle, half);
  1450.     if (comp(*middle, value)) {
  1451.         first = middle;
  1452.         ++first;
  1453.         len = len - half - 1;
  1454.     } else
  1455.         len = half;
  1456.     }
  1457.     return first;
  1458. }
  1459.  
  1460. template <class ForwardIterator, class T, class Compare, class Distance>
  1461. inline ForwardIterator __lower_bound(ForwardIterator first,
  1462.                      ForwardIterator last,
  1463.                      const T& value, Compare comp, Distance*,
  1464.                      bidirectional_iterator_tag) {
  1465.     return __lower_bound(first, last, value, comp, (Distance*)0,
  1466.              forward_iterator_tag());
  1467. }
  1468.  
  1469. template <class RandomAccessIterator, class T, class Compare, class Distance>
  1470. RandomAccessIterator __lower_bound(RandomAccessIterator first,
  1471.                    RandomAccessIterator last,
  1472.                    const T& value, Compare comp, Distance*,
  1473.                    random_access_iterator_tag) {
  1474.     Distance len = last - first;
  1475.     Distance half;
  1476.     RandomAccessIterator middle;
  1477.  
  1478.     while (len > 0) {
  1479.     half = len / 2;
  1480.     middle = first + half;
  1481.     if (comp(*middle, value)) {
  1482.         first = middle + 1;
  1483.         len = len - half - 1;
  1484.     } else
  1485.         len = half;
  1486.     }
  1487.     return first;
  1488. }
  1489.  
  1490. template <class ForwardIterator, class T, class Compare>
  1491. inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
  1492.                    const T& value, Compare comp) {
  1493.     return __lower_bound(first, last, value, comp, distance_type(first),
  1494.              iterator_category(first));
  1495. }
  1496.  
  1497. template <class ForwardIterator, class T, class Distance>
  1498. ForwardIterator __upper_bound(ForwardIterator first, ForwardIterator last,
  1499.                   const T& value, Distance*,
  1500.                   forward_iterator_tag) {
  1501.     Distance len = 0;
  1502.     distance(first, last, len);
  1503.     Distance half;
  1504.     ForwardIterator middle;
  1505.  
  1506.     while (len > 0) {
  1507.     half = len / 2;
  1508.     middle = first;
  1509.     advance(middle, half);
  1510.     if (value < *middle)
  1511.         len = half;
  1512.     else {
  1513.         first = middle;
  1514.         ++first;
  1515.         len = len - half - 1;
  1516.     }
  1517.     }
  1518.     return first;
  1519. }
  1520.  
  1521. template <class ForwardIterator, class T, class Distance>
  1522. inline ForwardIterator __upper_bound(ForwardIterator first,
  1523.                      ForwardIterator last,
  1524.                      const T& value, Distance*,
  1525.                      bidirectional_iterator_tag) {
  1526.     return __upper_bound(first, last, value, (Distance*)0,
  1527.              forward_iterator_tag());
  1528. }
  1529.  
  1530. template <class RandomAccessIterator, class T, class Distance>
  1531. RandomAccessIterator __upper_bound(RandomAccessIterator first,
  1532.                    RandomAccessIterator last, const T& value,
  1533.                    Distance*, random_access_iterator_tag) {
  1534.     Distance len = last - first;
  1535.     Distance half;
  1536.     RandomAccessIterator middle;
  1537.  
  1538.     while (len > 0) {
  1539.     half = len / 2;
  1540.     middle = first + half;
  1541.     if (value < *middle)
  1542.         len = half;
  1543.     else {
  1544.         first = middle + 1;
  1545.         len = len - half - 1;
  1546.     }
  1547.     }
  1548.     return first;
  1549. }
  1550.  
  1551. template <class ForwardIterator, class T>
  1552. inline ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
  1553.                    const T& value) {
  1554.     return __upper_bound(first, last, value, distance_type(first),
  1555.              iterator_category(first));
  1556. }
  1557.  
  1558. template <class ForwardIterator, class T, class Compare, class Distance>
  1559. ForwardIterator __upper_bound(ForwardIterator first, ForwardIterator last,
  1560.                   const T& value, Compare comp, Distance*,
  1561.                   forward_iterator_tag) {
  1562.     Distance len = 0;
  1563.     distance(first, last, len);
  1564.     Distance half;
  1565.     ForwardIterator middle;
  1566.  
  1567.     while (len > 0) {
  1568.     half = len / 2;
  1569.     middle = first;
  1570.     advance(middle, half);
  1571.     if (comp(value, *middle))
  1572.         len = half;
  1573.     else {
  1574.         first = middle;
  1575.         ++first;
  1576.         len = len - half - 1;
  1577.     }
  1578.     }
  1579.     return first;
  1580. }
  1581.  
  1582. template <class ForwardIterator, class T, class Compare, class Distance>
  1583. inline ForwardIterator __upper_bound(ForwardIterator first,
  1584.                      ForwardIterator last,
  1585.                      const T& value, Compare comp, Distance*,
  1586.                      bidirectional_iterator_tag) {
  1587.     return __upper_bound(first, last, value, comp, (Distance*)0,
  1588.              forward_iterator_tag());
  1589. }
  1590.  
  1591. template <class RandomAccessIterator, class T, class Compare, class Distance>
  1592. RandomAccessIterator __upper_bound(RandomAccessIterator first,
  1593.                    RandomAccessIterator last,
  1594.                    const T& value, Compare comp, Distance*,
  1595.                    random_access_iterator_tag) {
  1596.     Distance len = last - first;
  1597.     Distance half;
  1598.     RandomAccessIterator middle;
  1599.  
  1600.     while (len > 0) {
  1601.     half = len / 2;
  1602.     middle = first + half;
  1603.     if (comp(value, *middle))
  1604.         len = half;
  1605.     else {
  1606.         first = middle + 1;
  1607.         len = len - half - 1;
  1608.     }
  1609.     }
  1610.     return first;
  1611. }
  1612.  
  1613. template <class ForwardIterator, class T, class Compare>
  1614. inline ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
  1615.                    const T& value, Compare comp) {
  1616.     return __upper_bound(first, last, value, comp, distance_type(first),
  1617.              iterator_category(first));
  1618. }
  1619.  
  1620. template <class ForwardIterator, class T, class Distance>
  1621. pair<ForwardIterator, ForwardIterator>
  1622. __equal_range(ForwardIterator first, ForwardIterator last, const T& value,
  1623.           Distance*, forward_iterator_tag) {
  1624.     Distance len = 0;
  1625.     distance(first, last, len);
  1626.     Distance half;
  1627.     ForwardIterator middle, left, right;
  1628.  
  1629.     while (len > 0) {
  1630.     half = len / 2;
  1631.     middle = first;
  1632.     advance(middle, half);
  1633.     if (*middle < value) {
  1634.         first = middle;
  1635.         ++first;
  1636.         len = len - half - 1;
  1637.     } else if (value < *middle)
  1638.         len = half;
  1639.     else {
  1640.         left = lower_bound(first, middle, value);
  1641.         advance(first, len);
  1642.         right = upper_bound(++middle, first, value);
  1643.         return pair<ForwardIterator, ForwardIterator>(left, right);
  1644.     }
  1645.     }
  1646.     return pair<ForwardIterator, ForwardIterator>(first, first);
  1647. }
  1648.  
  1649. template <class ForwardIterator, class T, class Distance>
  1650. inline pair<ForwardIterator, ForwardIterator>
  1651. __equal_range(ForwardIterator first, ForwardIterator last, const T& value,
  1652.           Distance*, bidirectional_iterator_tag) {
  1653.     return __equal_range(first, last, value, (Distance*)0, 
  1654.              forward_iterator_tag());
  1655. }
  1656.  
  1657. template <class RandomAccessIterator, class T, class Distance>
  1658. pair<RandomAccessIterator, RandomAccessIterator>
  1659. __equal_range(RandomAccessIterator first, RandomAccessIterator last,
  1660.           const T& value, Distance*, random_access_iterator_tag) {
  1661.     Distance len = last - first;
  1662.     Distance half;
  1663.     RandomAccessIterator middle, left, right;
  1664.  
  1665.     while (len > 0) {
  1666.     half = len / 2;
  1667.     middle = first + half;
  1668.     if (*middle < value) {
  1669.         first = middle + 1;
  1670.         len = len - half - 1;
  1671.     } else if (value < *middle)
  1672.         len = half;
  1673.     else {
  1674.         left = lower_bound(first, middle, value);
  1675.         right = upper_bound(++middle, first + len, value);
  1676.         return pair<RandomAccessIterator, RandomAccessIterator>(left,
  1677.                                     right);
  1678.     }
  1679.     }
  1680.     return pair<RandomAccessIterator, RandomAccessIterator>(first, first);
  1681. }
  1682.  
  1683. template <class ForwardIterator, class T>
  1684. inline pair<ForwardIterator, ForwardIterator>
  1685. equal_range(ForwardIterator first, ForwardIterator last, const T& value) {
  1686.     return __equal_range(first, last, value, distance_type(first),
  1687.              iterator_category(first));
  1688. }
  1689.  
  1690. template <class ForwardIterator, class T, class Compare, class Distance>
  1691. pair<ForwardIterator, ForwardIterator>
  1692. __equal_range(ForwardIterator first, ForwardIterator last, const T& value,
  1693.           Compare comp, Distance*, forward_iterator_tag) {
  1694.     Distance len = 0;
  1695.     distance(first, last, len);
  1696.     Distance half;
  1697.     ForwardIterator middle, left, right;
  1698.  
  1699.     while (len > 0) {
  1700.     half = len / 2;
  1701.     middle = first;
  1702.     advance(middle, half);
  1703.     if (comp(*middle, value)) {
  1704.         first = middle;
  1705.         ++first;
  1706.         len = len - half - 1;
  1707.     } else if (comp(value, *middle))
  1708.         len = half;
  1709.     else {
  1710.         left = lower_bound(first, middle, value, comp);
  1711.         advance(first, len);
  1712.         right = upper_bound(++middle, first, value, comp);
  1713.         return pair<ForwardIterator, ForwardIterator>(left, right);
  1714.     }
  1715.     }
  1716.     return pair<ForwardIterator, ForwardIterator>(first, first);
  1717. }           
  1718.  
  1719. template <class ForwardIterator, class T, class Compare, class Distance>
  1720. inline pair<ForwardIterator, ForwardIterator>
  1721. __equal_range(ForwardIterator first, ForwardIterator last, const T& value,
  1722.           Compare comp, Distance*, bidirectional_iterator_tag) {
  1723.     return __equal_range(first, last, value, comp, (Distance*)0, 
  1724.              forward_iterator_tag());
  1725. }
  1726.  
  1727. template <class RandomAccessIterator, class T, class Compare, class Distance>
  1728. pair<RandomAccessIterator, RandomAccessIterator>
  1729. __equal_range(RandomAccessIterator first, RandomAccessIterator last,
  1730.           const T& value, Compare comp, Distance*,
  1731.           random_access_iterator_tag) {
  1732.     Distance len = last - first;
  1733.     Distance half;
  1734.     RandomAccessIterator middle, left, right;
  1735.  
  1736.     while (len > 0) {
  1737.     half = len / 2;
  1738.     middle = first + half;
  1739.     if (comp(*middle, value)) {
  1740.         first = middle + 1;
  1741.         len = len - half - 1;
  1742.     } else if (comp(value, *middle))
  1743.         len = half;
  1744.     else {
  1745.         left = lower_bound(first, middle, value, comp);
  1746.         right = upper_bound(++middle, first + len, value, comp);
  1747.         return pair<RandomAccessIterator, RandomAccessIterator>(left,
  1748.                                     right);
  1749.     }
  1750.     }
  1751.     return pair<RandomAccessIterator, RandomAccessIterator>(first, first);
  1752. }           
  1753.  
  1754. template <class ForwardIterator, class T, class Compare>
  1755. inline pair<ForwardIterator, ForwardIterator>
  1756. equal_range(ForwardIterator first, ForwardIterator last, const T& value,
  1757.         Compare comp) {
  1758.     return __equal_range(first, last, value, comp, distance_type(first),
  1759.              iterator_category(first));
  1760. }    
  1761.  
  1762. template <class ForwardIterator, class T>
  1763. bool binary_search(ForwardIterator first, ForwardIterator last,
  1764.            const T& value) {
  1765.     ForwardIterator i = lower_bound(first, last, value);
  1766.     return i != last && !(value < *i);
  1767. }
  1768.  
  1769. template <class ForwardIterator, class T, class Compare>
  1770. bool binary_search(ForwardIterator first, ForwardIterator last, const T& value,
  1771.            Compare comp) {
  1772.     ForwardIterator i = lower_bound(first, last, value, comp);
  1773.     return i != last && !comp(value, *i);
  1774. }
  1775.  
  1776. template <class InputIterator1, class InputIterator2, class OutputIterator>
  1777. OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
  1778.              InputIterator2 first2, InputIterator2 last2,
  1779.              OutputIterator result) {
  1780.     while (first1 != last1 && first2 != last2)
  1781.     if (*first2 < *first1)
  1782.         *result++ = *first2++;
  1783.     else
  1784.         *result++ = *first1++;
  1785.     return copy(first2, last2, copy(first1, last1, result));
  1786. }
  1787.  
  1788. template <class InputIterator1, class InputIterator2, class OutputIterator,
  1789.       class Compare>
  1790. OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
  1791.              InputIterator2 first2, InputIterator2 last2,
  1792.              OutputIterator result, Compare comp) {
  1793.     while (first1 != last1 && first2 != last2)
  1794.     if (comp(*first2, *first1))
  1795.         *result++ = *first2++;
  1796.     else
  1797.         *result++ = *first1++;
  1798.     return copy(first2, last2, copy(first1, last1, result));
  1799. }
  1800.  
  1801. template <class BidirectionalIterator, class Distance>
  1802. void __merge_without_buffer(BidirectionalIterator first,
  1803.                 BidirectionalIterator middle,
  1804.                 BidirectionalIterator last,
  1805.                 Distance len1, Distance len2) {
  1806.     if (len1 == 0 || len2 == 0) return;
  1807.     if (len1 + len2 == 2) {
  1808.     if (*middle < *first) iter_swap(first, middle);
  1809.     return;
  1810.     }
  1811.     BidirectionalIterator first_cut = first;
  1812.     BidirectionalIterator second_cut = middle;
  1813.     Distance len11 = 0;
  1814.     Distance len22 = 0;
  1815.     if (len1 > len2) {
  1816.     len11 = len1 / 2;
  1817.     advance(first_cut, len11);
  1818.     second_cut = lower_bound(middle, last, *first_cut);
  1819.     distance(middle, second_cut, len22);
  1820.     } else {
  1821.     len22 = len2 / 2;
  1822.     advance(second_cut, len22);
  1823.     first_cut = upper_bound(first, middle, *second_cut);
  1824.     distance(first, first_cut, len11);
  1825.     }
  1826.     rotate(first_cut, middle, second_cut);
  1827.     BidirectionalIterator new_middle = first_cut;
  1828.     advance(new_middle, len22);
  1829.     __merge_without_buffer(first, first_cut, new_middle, len11, len22);
  1830.     __merge_without_buffer(new_middle, second_cut, last, len1 - len11,
  1831.                len2 - len22);
  1832. }
  1833.  
  1834. template <class BidirectionalIterator, class Distance, class Compare>
  1835. void __merge_without_buffer(BidirectionalIterator first,
  1836.                 BidirectionalIterator middle,
  1837.                 BidirectionalIterator last,
  1838.                 Distance len1, Distance len2, Compare comp) {
  1839.     if (len1 == 0 || len2 == 0) return;
  1840.     if (len1 + len2 == 2) {
  1841.     if (comp(*middle, *first)) iter_swap(first, middle);
  1842.     return;
  1843.     }
  1844.     BidirectionalIterator first_cut = first;
  1845.     BidirectionalIterator second_cut = middle;
  1846.     Distance len11 = 0;
  1847.     Distance len22 = 0;
  1848.     if (len1 > len2) {
  1849.     len11 = len1 / 2;
  1850.     advance(first_cut, len11);
  1851.     second_cut = lower_bound(middle, last, *first_cut, comp);
  1852.     distance(middle, second_cut, len22);
  1853.     } else {
  1854.     len22 = len2 / 2;
  1855.     advance(second_cut, len22);
  1856.     first_cut = upper_bound(first, middle, *second_cut, comp);
  1857.     distance(first, first_cut, len11);
  1858.     }
  1859.     rotate(first_cut, middle, second_cut);
  1860.     BidirectionalIterator new_middle = first_cut;
  1861.     advance(new_middle, len22);
  1862.     __merge_without_buffer(first, first_cut, new_middle, len11, len22, comp);
  1863.     __merge_without_buffer(new_middle, second_cut, last, len1 - len11,
  1864.                len2 - len22, comp);
  1865. }
  1866.  
  1867.  
  1868. template <class InputIterator, class OutputIterator>
  1869. OutputIterator __borland_bugfix_copy(InputIterator first, InputIterator last,
  1870.             OutputIterator result) {
  1871. // this is used in __rotate_adaptive to work around some obscure Borland
  1872. // bug. It is the same as copy, but with a different (and appropriate) name.
  1873.     while (first != last) *result++ = *first++;
  1874.     return result;
  1875. }
  1876.  
  1877. template <class BidirectionalIterator1, class BidirectionalIterator2,
  1878.       class Distance>
  1879. BidirectionalIterator1 __rotate_adaptive(BidirectionalIterator1 first,
  1880.                      BidirectionalIterator1 middle,
  1881.                      BidirectionalIterator1 last,
  1882.                      Distance len1, Distance len2,
  1883.                      BidirectionalIterator2 buffer,
  1884.                      Distance buffer_size) {
  1885.     BidirectionalIterator2 buffer_end;
  1886.     if (len1 > len2 && len2 <= buffer_size) {
  1887.     buffer_end = __borland_bugfix_copy(middle, last, buffer);
  1888.     copy_backward(first, middle, last);
  1889.     return copy(buffer, buffer_end, first);
  1890.     } else if (len1 <= buffer_size) {
  1891.     buffer_end = __borland_bugfix_copy(first, middle, buffer);
  1892.     copy(middle, last, first);
  1893.     return copy_backward(buffer, buffer_end, last);
  1894.     } else  {
  1895.     rotate(first, middle, last);
  1896.     advance(first, len2);
  1897.     return first;
  1898.     }
  1899. }
  1900.  
  1901. template <class BidirectionalIterator1, class BidirectionalIterator2,
  1902.       class BidirectionalIterator3>
  1903. BidirectionalIterator3 __merge_backward(BidirectionalIterator1 first1,
  1904.                     BidirectionalIterator1 last1,
  1905.                     BidirectionalIterator2 first2,
  1906.                     BidirectionalIterator2 last2,
  1907.                     BidirectionalIterator3 result) {
  1908.     if (first1 == last1) return copy_backward(first2, last2, result);
  1909.     if (first2 == last2) return copy_backward(first1, last1, result);
  1910.     --last1;
  1911.     --last2;
  1912.     while (true) {
  1913.     if (*last2 < *last1) {
  1914.         *--result = *last1;
  1915.         if (first1 == last1) return copy_backward(first2, ++last2, result);
  1916.         --last1;
  1917.     } else {
  1918.         *--result = *last2;
  1919.         if (first2 == last2) return copy_backward(first1, ++last1, result);
  1920.         --last2;
  1921.     }
  1922.     }
  1923. }
  1924.  
  1925. template <class BidirectionalIterator1, class BidirectionalIterator2,
  1926.       class BidirectionalIterator3, class Compare>
  1927. BidirectionalIterator3 __merge_backward(BidirectionalIterator1 first1,
  1928.                     BidirectionalIterator1 last1,
  1929.                     BidirectionalIterator2 first2,
  1930.                     BidirectionalIterator2 last2,
  1931.                     BidirectionalIterator3 result,
  1932.                     Compare comp) {
  1933.     if (first1 == last1) return copy_backward(first2, last2, result);
  1934.     if (first2 == last2) return copy_backward(first1, last1, result);
  1935.     --last1;
  1936.     --last2;
  1937.     while (true) {
  1938.     if (comp(*last2, *last1)) {
  1939.         *--result = *last1;
  1940.         if (first1 == last1) return copy_backward(first2, ++last2, result);
  1941.         --last1;
  1942.     } else {
  1943.         *--result = *last2;
  1944.         if (first2 == last2) return copy_backward(first1, ++last1, result);
  1945.         --last2;
  1946.     }
  1947.     }
  1948. }
  1949.  
  1950. template <class BidirectionalIterator, class Distance, class Pointer, class T>
  1951. void __merge_adaptive(BidirectionalIterator first, 
  1952.               BidirectionalIterator middle, 
  1953.               BidirectionalIterator last, Distance len1, Distance len2,
  1954.               Pointer buffer, Distance buffer_size,
  1955.               Distance& fill_pointer, T*) {
  1956.     if (len1 <= len2 && len1 <= buffer_size) {
  1957.     BidirectionalIterator i = first;
  1958.     Pointer j = buffer;
  1959.     len2 = 0;
  1960.     while (len2 < len1 && len2 < fill_pointer) {
  1961.         *buffer++ = *first++;
  1962.         ++len2;
  1963.     }
  1964.     raw_storage_iterator<Pointer, T> end_buffer = buffer;
  1965.     while (len2++ < len1) {
  1966.         *end_buffer++ = *first++;
  1967.         ++fill_pointer;
  1968.     }
  1969.     merge(j, j + len1, middle, last, i);
  1970.     } else if (len2 <= buffer_size) {
  1971.     BidirectionalIterator i = middle;
  1972.     Pointer j = buffer;
  1973.     len1 = 0;
  1974.     while (len1 < len2 && len1 < fill_pointer) {
  1975.         *buffer++ = *middle++;
  1976.         ++len1;
  1977.     }
  1978.     raw_storage_iterator<Pointer, T> end_buffer = buffer;
  1979.     while (len1++ < len2) {
  1980.         *end_buffer++ = *middle++;
  1981.         ++fill_pointer;
  1982.     }
  1983.     __merge_backward(first, i, j, j + len2, last);
  1984.     } else {
  1985.     BidirectionalIterator first_cut = first;
  1986.     BidirectionalIterator second_cut = middle;
  1987.     Distance len11 = 0;
  1988.     Distance len22 = 0;
  1989.     if (len1 > len2) {
  1990.         len11 = len1 / 2;
  1991.         advance(first_cut, len11);
  1992.         second_cut = lower_bound(middle, last, *first_cut);
  1993.         distance(middle, second_cut, len22);   
  1994.     } else {
  1995.         len22 = len2 / 2;
  1996.         advance(second_cut, len22);
  1997.         first_cut = upper_bound(first, middle, *second_cut);
  1998.         distance(first, first_cut, len11);
  1999.     }
  2000.     BidirectionalIterator new_middle =
  2001.         __rotate_adaptive(first_cut, middle, second_cut, len1 - len11,
  2002.                   len22, buffer, buffer_size);
  2003.     __merge_adaptive(first, first_cut, new_middle, len11, len22, buffer,
  2004.              buffer_size, fill_pointer, (T*)0);
  2005.     __merge_adaptive(new_middle, second_cut, last, len1 - len11,
  2006.              len2 - len22, buffer, buffer_size, fill_pointer,
  2007.              (T*)0);
  2008.     }
  2009. }
  2010.  
  2011. template <class BidirectionalIterator, class Distance, class Pointer, class T,
  2012.       class Compare>
  2013. void __merge_adaptive(BidirectionalIterator first, 
  2014.               BidirectionalIterator middle, 
  2015.               BidirectionalIterator last, Distance len1, Distance len2,
  2016.               Pointer buffer, Distance buffer_size,
  2017.               Distance& fill_pointer, T*, Compare comp) {
  2018.     if (len1 <= len2 && len1 <= buffer_size) {
  2019.     BidirectionalIterator i = first;
  2020.     Pointer j = buffer;
  2021.     len2 = 0;
  2022.     while (len2 < len1 && len2 < fill_pointer) {
  2023.         *buffer++ = *first++;
  2024.         ++len2;
  2025.     }
  2026.     raw_storage_iterator<Pointer, T> end_buffer = buffer;
  2027.     while (len2++ < len1) {
  2028.         *end_buffer++ = *first++;
  2029.         ++fill_pointer;
  2030.     }
  2031.     merge(j, j + len1, middle, last, i, comp);
  2032.     } else if (len2 <= buffer_size) {
  2033.     BidirectionalIterator i = middle;
  2034.     Pointer j = buffer;
  2035.     len1 = 0;
  2036.     while (len1 < len2 && len1 < fill_pointer) {
  2037.         *buffer++ = *middle++;
  2038.         ++len1;
  2039.     }
  2040.     raw_storage_iterator<Pointer, T> end_buffer = buffer;
  2041.     while (len1++ < len2) {
  2042.         *end_buffer++ = *middle++;
  2043.         ++fill_pointer;
  2044.     }
  2045.     __merge_backward(first, i, j, j + len2, last, comp);
  2046.     } else {
  2047.     BidirectionalIterator first_cut = first;
  2048.     BidirectionalIterator second_cut = middle;
  2049.     Distance len11 = 0;
  2050.     Distance len22 = 0;
  2051.     if (len1 > len2) {
  2052.         len11 = len1 / 2;
  2053.         advance(first_cut, len11);
  2054.         second_cut = lower_bound(middle, last, *first_cut, comp);
  2055.         distance(middle, second_cut, len22);   
  2056.     } else {
  2057.         len22 = len2 / 2;
  2058.         advance(second_cut, len22);
  2059.         first_cut = upper_bound(first, middle, *second_cut, comp);
  2060.         distance(first, first_cut, len11);
  2061.     }
  2062.     BidirectionalIterator new_middle =
  2063.         __rotate_adaptive(first_cut, middle, second_cut, len1 - len11,
  2064.                   len22, buffer, buffer_size);
  2065.     __merge_adaptive(first, first_cut, new_middle, len11, len22, buffer,
  2066.              buffer_size, fill_pointer, (T*)0, comp);
  2067.     __merge_adaptive(new_middle, second_cut, last, len1 - len11,
  2068.              len2 - len22, buffer, buffer_size, fill_pointer,
  2069.              (T*)0, comp);
  2070.     }
  2071. }
  2072.  
  2073. template <class BidirectionalIterator, class Distance, class Pointer>
  2074. void __inplace_merge(BidirectionalIterator first,
  2075.              BidirectionalIterator middle, 
  2076.              BidirectionalIterator last, Distance len1, Distance len2,
  2077.              pair<Pointer, Distance> p) {
  2078.     if (p.first == 0) {
  2079.     __merge_without_buffer(first, middle, last, len1, len2);
  2080.     return;
  2081.     }
  2082.     Distance fill_pointer = 0;
  2083.     __merge_adaptive(first, middle, last, len1, len2, p.first, p.second,
  2084.              fill_pointer, value_type(first)); 
  2085.     destroy(p.first, p.first + fill_pointer);
  2086.     return_temporary_buffer(p.first);
  2087. }
  2088.  
  2089. template <class BidirectionalIterator, class Distance, class Pointer, 
  2090.       class Compare>
  2091. void __inplace_merge(BidirectionalIterator first,
  2092.              BidirectionalIterator middle, 
  2093.              BidirectionalIterator last, Distance len1, Distance len2,
  2094.              pair<Pointer, Distance> p, Compare comp) {
  2095.     if (p.first == 0) {
  2096.     __merge_without_buffer(first, middle, last, len1, len2, comp);
  2097.     return;
  2098.     }
  2099.     Distance fill_pointer = 0;
  2100.     __merge_adaptive(first, middle, last, len1, len2, p.first, p.second,
  2101.              fill_pointer, value_type(first), comp); 
  2102.     destroy(p.first, p.first + fill_pointer);
  2103.     return_temporary_buffer(p.first);
  2104. }
  2105.  
  2106. template <class BidirectionalIterator, class Distance>
  2107. inline void __inplace_merge_aux(BidirectionalIterator first,
  2108.                 BidirectionalIterator middle,
  2109.                 BidirectionalIterator last, Distance*) {
  2110.     Distance len1 = 0;
  2111.     distance(first, middle, len1);
  2112.     Distance len2 = 0;
  2113.     distance(middle, last, len2);
  2114.     __inplace_merge(first, middle, last, len1, len2,
  2115.             get_temporary_buffer(len1 + len2, value_type(first)));
  2116. }
  2117.  
  2118. template <class BidirectionalIterator, class Distance, class Compare>
  2119. inline void __inplace_merge_aux(BidirectionalIterator first,
  2120.                 BidirectionalIterator middle,
  2121.                 BidirectionalIterator last, Distance*,
  2122.                 Compare comp) {
  2123.     Distance len1 = 0;
  2124.     distance(first, middle, len1);
  2125.     Distance len2 = 0;
  2126.     distance(middle, last, len2);
  2127.     __inplace_merge(first, middle, last, len1, len2,
  2128.             get_temporary_buffer(len1 + len2, value_type(first)),
  2129.             comp);
  2130. }
  2131.  
  2132. template <class BidirectionalIterator>
  2133. inline void inplace_merge(BidirectionalIterator first,
  2134.               BidirectionalIterator middle,
  2135.               BidirectionalIterator last) {
  2136.     __inplace_merge_aux(first, middle, last, distance_type(first));
  2137. }
  2138.  
  2139. template <class BidirectionalIterator, class Compare>
  2140. inline void inplace_merge(BidirectionalIterator first,
  2141.               BidirectionalIterator middle,
  2142.               BidirectionalIterator last, Compare comp) {
  2143.     __inplace_merge_aux(first, middle, last, distance_type(first), comp);
  2144. }
  2145.  
  2146. template <class InputIterator1, class InputIterator2>
  2147. bool includes(InputIterator1 first1, InputIterator1 last1,
  2148.           InputIterator2 first2, InputIterator2 last2) {
  2149.     while (first1 != last1 && first2 != last2)
  2150.     if (*first2 < *first1)
  2151.         return false;
  2152.     else if(*first1 < *first2) 
  2153.         ++first1;
  2154.     else
  2155.         ++first1, ++first2;
  2156.  
  2157.     return first2 == last2;
  2158. }
  2159.  
  2160. template <class InputIterator1, class InputIterator2, class Compare>
  2161. bool includes(InputIterator1 first1, InputIterator1 last1,
  2162.           InputIterator2 first2, InputIterator2 last2, Compare comp) {
  2163.     while (first1 != last1 && first2 != last2)
  2164.     if (comp(*first2, *first1))
  2165.         return false;
  2166.     else if(comp(*first1, *first2)) 
  2167.         ++first1;
  2168.     else
  2169.         ++first1, ++first2;
  2170.  
  2171.     return first2 == last2;
  2172. }
  2173.  
  2174. template <class InputIterator1, class InputIterator2, class OutputIterator>
  2175. OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
  2176.              InputIterator2 first2, InputIterator2 last2,
  2177.              OutputIterator result) {
  2178.     while (first1 != last1 && first2 != last2)
  2179.     if (*first1 < *first2)
  2180.         *result++ = *first1++;
  2181.     else if (*first2 < *first1)
  2182.         *result++ = *first2++;
  2183.     else {
  2184.         *result++ = *first1++;
  2185.         first2++;
  2186.     }
  2187.     return copy(first2, last2, copy(first1, last1, result));
  2188. }
  2189.  
  2190. template <class InputIterator1, class InputIterator2, class OutputIterator,
  2191.       class Compare>
  2192. OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
  2193.              InputIterator2 first2, InputIterator2 last2,
  2194.              OutputIterator result, Compare comp) {
  2195.     while (first1 != last1 && first2 != last2)
  2196.     if (comp(*first1, *first2))
  2197.         *result++ = *first1++;
  2198.     else if (comp(*first2, *first1))
  2199.         *result++ = *first2++;
  2200.     else {
  2201.         *result++ = *first1++;
  2202.         ++first2;
  2203.     }
  2204.     return copy(first2, last2, copy(first1, last1, result));
  2205. }
  2206.  
  2207. template <class InputIterator1, class InputIterator2, class OutputIterator>
  2208. OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
  2209.                 InputIterator2 first2, InputIterator2 last2,
  2210.                 OutputIterator result) {
  2211.     while (first1 != last1 && first2 != last2)
  2212.     if (*first1 < *first2)
  2213.         ++first1;
  2214.     else if (*first2 < *first1)
  2215.         ++first2;
  2216.     else {
  2217.         *result++ = *first1++;
  2218.         ++first2;
  2219.     }
  2220.     return result;
  2221. }
  2222.  
  2223. template <class InputIterator1, class InputIterator2, class OutputIterator,
  2224.       class Compare>
  2225. OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
  2226.                 InputIterator2 first2, InputIterator2 last2,
  2227.                 OutputIterator result, Compare comp) {
  2228.     while (first1 != last1 && first2 != last2)
  2229.     if (comp(*first1, *first2))
  2230.         ++first1;
  2231.     else if (comp(*first2, *first1))
  2232.         ++first2;
  2233.     else {
  2234.         *result++ = *first1++;
  2235.         ++first2;
  2236.     }
  2237.     return result;
  2238. }
  2239.  
  2240. template <class InputIterator1, class InputIterator2, class OutputIterator>
  2241. OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
  2242.                   InputIterator2 first2, InputIterator2 last2,
  2243.                   OutputIterator result) {
  2244.     while (first1 != last1 && first2 != last2)
  2245.     if (*first1 < *first2)
  2246.         *result++ = *first1++;
  2247.     else if (*first2 < *first1)
  2248.         ++first2;
  2249.     else {
  2250.         ++first1;
  2251.         ++first2;
  2252.     }
  2253.     return copy(first1, last1, result);
  2254. }
  2255.  
  2256. template <class InputIterator1, class InputIterator2, class OutputIterator, 
  2257.       class Compare>
  2258. OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
  2259.                   InputIterator2 first2, InputIterator2 last2, 
  2260.                   OutputIterator result, Compare comp) {
  2261.     while (first1 != last1 && first2 != last2)
  2262.     if (comp(*first1, *first2))
  2263.         *result++ = *first1++;
  2264.     else if (comp(*first2, *first1))
  2265.         ++first2;
  2266.     else {
  2267.         ++first1;
  2268.         ++first2;
  2269.     }
  2270.     return copy(first1, last1, result);
  2271. }
  2272.  
  2273. template <class InputIterator1, class InputIterator2, class OutputIterator>
  2274. OutputIterator set_symmetric_difference(InputIterator1 first1,
  2275.                     InputIterator1 last1,
  2276.                     InputIterator2 first2,
  2277.                     InputIterator2 last2,
  2278.                     OutputIterator result) {
  2279.     while (first1 != last1 && first2 != last2)
  2280.     if (*first1 < *first2)
  2281.         *result++ = *first1++;
  2282.     else if (*first2 < *first1)
  2283.         *result++ = *first2++;
  2284.     else {
  2285.         ++first1;
  2286.         ++first2;
  2287.     }
  2288.     return copy(first2, last2, copy(first1, last1, result));
  2289. }
  2290.  
  2291. template <class InputIterator1, class InputIterator2, class OutputIterator,
  2292.       class Compare>
  2293. OutputIterator set_symmetric_difference(InputIterator1 first1,
  2294.                     InputIterator1 last1,
  2295.                     InputIterator2 first2,
  2296.                     InputIterator2 last2,
  2297.                     OutputIterator result, Compare comp) {
  2298.     while (first1 != last1 && first2 != last2)
  2299.     if (comp(*first1, *first2))
  2300.         *result++ = *first1++;
  2301.     else if (comp(*first2, *first1))
  2302.         *result++ = *first2++;
  2303.     else {
  2304.         ++first1;
  2305.         ++first2;
  2306.     }
  2307.     return copy(first2, last2, copy(first1, last1, result));
  2308. }
  2309.  
  2310. template <class InputIterator>
  2311. InputIterator max_element(InputIterator first, InputIterator last) {
  2312.     if (first == last) return first;
  2313.     InputIterator result = first;
  2314.     while (++first != last) 
  2315.     if (*result < *first) result = first;
  2316.     return result;
  2317. }
  2318.  
  2319. template <class InputIterator, class Compare>
  2320. InputIterator max_element(InputIterator first, InputIterator last,
  2321.               Compare comp) {
  2322.     if (first == last) return first;
  2323.     InputIterator result = first;
  2324.     while (++first != last) 
  2325.     if (comp(*result, *first)) result = first;
  2326.     return result;
  2327. }
  2328.  
  2329. template <class InputIterator>
  2330. InputIterator min_element(InputIterator first, InputIterator last) {
  2331.     if (first == last) return first;
  2332.     InputIterator result = first;
  2333.     while (++first != last) 
  2334.     if (*first < *result) result = first;
  2335.     return result;
  2336. }
  2337.  
  2338. template <class InputIterator, class Compare>
  2339. InputIterator min_element(InputIterator first, InputIterator last,
  2340.               Compare comp) {
  2341.     if (first == last) return first;
  2342.     InputIterator result = first;
  2343.     while (++first != last) 
  2344.     if (comp(*first, *result)) result = first;
  2345.     return result;
  2346. }
  2347.  
  2348. template <class BidirectionalIterator>
  2349. bool next_permutation(BidirectionalIterator first,
  2350.               BidirectionalIterator last) {
  2351.     if (first == last) return false;
  2352.     BidirectionalIterator i = first;
  2353.     ++i;
  2354.     if (i == last) return false;
  2355.     i = last;
  2356.     --i;
  2357.  
  2358.     for(;;) {
  2359.     BidirectionalIterator ii = i--;
  2360.     if (*i < *ii) {
  2361.         BidirectionalIterator j = last;
  2362.         while (!(*i < *--j));
  2363.         iter_swap(i, j);
  2364.         reverse(ii, last);
  2365.         return true;
  2366.     }
  2367.     if (i == first) {
  2368.         reverse(first, last);
  2369.         return false;
  2370.     }
  2371.     }
  2372. }
  2373.  
  2374. template <class BidirectionalIterator, class Compare>
  2375. bool next_permutation(BidirectionalIterator first, BidirectionalIterator last,
  2376.               Compare comp) {
  2377.     if (first == last) return false;
  2378.     BidirectionalIterator i = first;
  2379.     ++i;
  2380.     if (i == last) return false;
  2381.     i = last;
  2382.     --i;
  2383.  
  2384.     for(;;) {
  2385.     BidirectionalIterator ii = i--;
  2386.     if (comp(*i, *ii)) {
  2387.         BidirectionalIterator j = last;
  2388.         while (!comp(*i, *--j));
  2389.         iter_swap(i, j);
  2390.         reverse(ii, last);
  2391.         return true;
  2392.     }
  2393.     if (i == first) {
  2394.         reverse(first, last);
  2395.         return false;
  2396.     }
  2397.     }
  2398. }
  2399.  
  2400. template <class BidirectionalIterator>
  2401. bool prev_permutation(BidirectionalIterator first,
  2402.               BidirectionalIterator last) {
  2403.     if (first == last) return false;
  2404.     BidirectionalIterator i = first;
  2405.     ++i;
  2406.     if (i == last) return false;
  2407.     i = last;
  2408.     --i;
  2409.  
  2410.     for(;;) {
  2411.     BidirectionalIterator ii = i--;
  2412.     if (!(*i < *ii)) {
  2413.         BidirectionalIterator j = last;
  2414.         while (*i < *--j);
  2415.         iter_swap(i, j);
  2416.         reverse(ii, last);
  2417.         return true;
  2418.     }
  2419.     if (i == first) {
  2420.         reverse(first, last);
  2421.         return false;
  2422.     }
  2423.     }
  2424. }
  2425.  
  2426. template <class BidirectionalIterator, class Compare>
  2427. bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last,
  2428.               Compare comp) {
  2429.     if (first == last) return false;
  2430.     BidirectionalIterator i = first;
  2431.     ++i;
  2432.     if (i == last) return false;
  2433.     i = last;
  2434.     --i;
  2435.  
  2436.     for(;;) {
  2437.     BidirectionalIterator ii = i--;
  2438.     if (!comp(*i, *ii)) {
  2439.         BidirectionalIterator j = last;
  2440.         while (comp(*i, *--j));
  2441.         iter_swap(i, j);
  2442.         reverse(ii, last);
  2443.         return true;
  2444.     }
  2445.     if (i == first) {
  2446.         reverse(first, last);
  2447.         return false;
  2448.     }
  2449.     }
  2450. }
  2451.  
  2452. template <class InputIterator, class T>
  2453. T accumulate(InputIterator first, InputIterator last, T init) {
  2454.     while (first != last) 
  2455.     init = init + *first++;
  2456.     return init;
  2457. }
  2458.  
  2459. template <class InputIterator, class T, class BinaryOperation>
  2460. T accumulate(InputIterator first, InputIterator last, T init,
  2461.          BinaryOperation binary_op) {
  2462.     while (first != last) 
  2463.     init = binary_op(init, *first++);
  2464.     return init;
  2465. }
  2466.  
  2467. template <class InputIterator1, class InputIterator2, class T>
  2468. T inner_product(InputIterator1 first1, InputIterator1 last1,
  2469.         InputIterator2 first2, T init) {
  2470.     while (first1 != last1) 
  2471.     init = init + (*first1++ * *first2++);
  2472.     return init;
  2473. }
  2474.  
  2475. template <class InputIterator1, class InputIterator2, class T,
  2476.       class BinaryOperation1, class BinaryOperation2>
  2477. T inner_product(InputIterator1 first1, InputIterator1 last1,
  2478.         InputIterator2 first2, T init, BinaryOperation1 binary_op1,
  2479.         BinaryOperation2 binary_op2) {
  2480.     while (first1 != last1) 
  2481.     init = binary_op1(init, binary_op2(*first1++, *first2++));
  2482.     return init;
  2483. }
  2484.  
  2485. template <class InputIterator, class OutputIterator, class T>
  2486. OutputIterator __partial_sum(InputIterator first, InputIterator last,
  2487.                  OutputIterator result, T*) {
  2488.     T value = *first;
  2489.     while (++first != last) {
  2490.     value = value + *first;
  2491.     *++result = value;
  2492.     }
  2493.     return ++result;
  2494. }
  2495.  
  2496. template <class InputIterator, class OutputIterator>
  2497. OutputIterator partial_sum(InputIterator first, InputIterator last,
  2498.                OutputIterator result) {
  2499.     if (first == last) return result;
  2500.     *result = *first;
  2501.     return __partial_sum(first, last, result, value_type(first));
  2502. }
  2503.  
  2504. template <class InputIterator, class OutputIterator, class T,
  2505.       class BinaryOperation>
  2506. OutputIterator __partial_sum(InputIterator first, InputIterator last,
  2507.                  OutputIterator result, T*,
  2508.                  BinaryOperation binary_op) {
  2509.     T value = *first;
  2510.     while (++first != last) {
  2511.     value = binary_op(value, *first);
  2512.     *++result = value;
  2513.     }
  2514.     return ++result;
  2515. }
  2516.  
  2517. template <class InputIterator, class OutputIterator, class BinaryOperation>
  2518. OutputIterator partial_sum(InputIterator first, InputIterator last,
  2519.                OutputIterator result, BinaryOperation binary_op) {
  2520.     if (first == last) return result;
  2521.     *result = *first;
  2522.     return __partial_sum(first, last, result, value_type(first), binary_op);
  2523. }
  2524.  
  2525. template <class InputIterator, class OutputIterator, class T>
  2526. OutputIterator __adjacent_difference(InputIterator first, InputIterator last, 
  2527.                      OutputIterator result, T*) {
  2528.     T value = *first;
  2529.     while (++first != last) {
  2530.     T tmp = *first;
  2531.     *++result = tmp - value;
  2532.     value = tmp;
  2533.     }
  2534.     return ++result;
  2535. }
  2536.  
  2537. template <class InputIterator, class OutputIterator>
  2538. OutputIterator adjacent_difference(InputIterator first, InputIterator last, 
  2539.                    OutputIterator result) {
  2540.     if (first == last) return result;
  2541.     *result = *first;
  2542.     return __adjacent_difference(first, last, result, value_type(first));
  2543. }
  2544.  
  2545. template <class InputIterator, class OutputIterator, class T, 
  2546.       class BinaryOperation>
  2547. OutputIterator __adjacent_difference(InputIterator first, InputIterator last, 
  2548.                      OutputIterator result, T*,
  2549.                      BinaryOperation binary_op) {
  2550.     T value = *first;
  2551.     while (++first != last) {
  2552.     T tmp = *first;
  2553.     *++result = binary_op(tmp, value);
  2554.     value = tmp;
  2555.     }
  2556.     return ++result;
  2557. }
  2558.  
  2559. template <class InputIterator, class OutputIterator, class BinaryOperation>
  2560. OutputIterator adjacent_difference(InputIterator first, InputIterator last,
  2561.                    OutputIterator result,
  2562.                    BinaryOperation binary_op) {
  2563.     if (first == last) return result;
  2564.     *result = *first;
  2565.     return __adjacent_difference(first, last, result, value_type(first),
  2566.                  binary_op);
  2567. }
  2568.  
  2569. template <class ForwardIterator, class T>
  2570. void iota(ForwardIterator first, ForwardIterator last, T value) {
  2571.     while (first != last) *first++ = value++;
  2572. }
  2573.  
  2574. #endif
  2575.  
  2576.